CSCI 311
Graph Definitions

  1. graph - a graph G is a collection of two sets:V, a set of nodes called vertices and G, a set of branches (edges) that connect the vertices
  2. directed graph or digraph - <v1, v2> - graph in which each edge is associated with an ordered pair of vertices
  3. undirected graph or graph - graph in which each edge is associated with an unordered pair of vertices
  4. adjacent - a vertex v1 in a graph G is adjacent to v2 if there is an edge between v1 to v2
  5. adjacent - a vertex v1 in a digraph G is adjacent to v2 if there is a directed edge from vertex v1 to vertex v2
  6. path - sequence of vertices v1, v2, v3,…vn where there is an edge from vi to vi+1
  7. cycle path - path from vertex to itself
  8. simple path - path in which all vertices except possibly first and last are distinct
  9. cycle - simple path in which first and last vertices are the same
  10. acyclic graph - graph with no cycles
  11. tree - connected, acyclic graph with a specially designated node called the root
  12. connected graph - there is a path between any two vertices (undirected)
  13. strongly connected - there is a path between any two vertices (digraph)
  14. weakly connected - there is a path from vertex I to vertex J or from vertex J to vertex I (digraph)
  15. outdegree of a node - number of edges extending from the node (digraph)
  16. indegree of a node - number of edges entering a node (digraph)
  17. degree of a node - number of edges incident to a node (undirected)
  18. complete graph (undirected) - a graph is complete if each pair of distinct vertices has an edge between them (graph with n vertices and exactly n(n-1)/2 edges)
  19. complete directed graph - a directed graph with exactly n(n-1) edges
  20. weighted graph - graph in which the edges represent numeric values
  21. directed path - sequence of directed edges between two vertices
  22. multigraph - figure which has multiple occurrences of the same edge (2 or more edges between2 vertices)
  23. network - graph in which each edge has an associated positive numerical weight
  24. A graph with n vertices and exactly n(n-1)/2 edges is called complete
  25. depth first search (DFS) - a graph traversal strategy in which a path from a vertex v proceeds as deeply into the graph as possible before backing up
  26. breadth-first search (BFS) a graph traversal strategy in which a path from a vertex v visits every vertex adjacent to v that it can before visiting any other vertex
  27. topological order - linear ordering of the vertices in a digraph in which vertex x precedes vertex y if there is a directed edge from x to y in the graph
  28. topological sort - technique for arranging the vertices into topological order
  29. spanning tree - a spanning tree of a connected undirected graph G is a subgraph of G that contains all of G's vertices and enough of its edges to form a tree
  30. DFS spanning tree - spanning tree created by executing a depth-first search of a graph's vertices
  31. BFS spanning tree - spanning tree created by executing a breadth-first search of a graph's vertices
  32. minimum spanning tree - spanning tree of a weighted, connected, undirected graph which has minimal edge-weight sum
  33. shortest path - the shortest path between two given vertices in a weighted graph is the path that has the smallest sum of its edge weights
  34. Euler circuit - a path in an undirected graph that begins at a vertex v, passes through every edge in the graph exactly once, and terminates at v
  35. Hamilton circuit - a path that begins at a vertex v, passes through every vertex in the graph exactly once, and terminates at v.
  36. Traveling salesman problem
  37. Three utilities problem
  38. Four-color problem