Graph Theory

  1. Network
    Destinations with their connecting links
  2. Euler circuit problems
    problems questioning routes and backtracking
  3. Graph Theory
    the study of circuit and routing problems
  4. graph
    collection of one or more points(vertices) and the connections between them(edges)
  5. Vertices
    connections on a graph
  6. Vertex
    Connection on a graph {singular}
  7. edges
    connections on a graph eithier straight or curved
  8. loop
    edge that connec ts to itself with only one vertex
  9. adjacent vertices
    two vertices ina graph connected by an edge
  10. T/F? A vertex may be adjacent to itself
  11. Degree of a vertex
    Total number of edges at a vertex
  12. How do you find the degree of a vertex?
    Count the number or segments or arches "coming out" of the vertex
  13. path
    route that passes from one vertex to an adjacent vertex, and each edge connecting an adjacent vertex is used, at most, once
  14. Euler path
    path that uses every edge of a graph exactly once
  15. circuit
    path that ends at the same vertex in which it started
  16. Euler circuit
    circuit that uses every edge of a graph exactly once
  17. connected
    graph in which you can travel from any vertice to any other in the graph
  18. disconnected
    a graph in which is not connected
  19. components
    seperate pieces of a graph that cannot be enlarged while remaining connected
  20. bridge
    edge in a connected graph, in which the removal of would leave behind a graph that is disconnected
  21. edge-walker algorithm
    gives optimal eulerization for a rectangular path
  22. If d is the sum of degrees of all vertices and e is the number of edges in a graph, then: (equation)
  23. multigraph
    more than one edge connecting two vertice
  24. Connected graph has a Euler Cycle/Circuit if and only if each of its vertices have an even degree
  25. Splicing
    Is a simple way to make a circuit, rather than using Fleury's Algorithm
Card Set
Graph Theory
Graph theory 6.1