Graph Terminology

• graph - a graph G is a collection of two sets: V, a set of vertices and E, a set of edges that connect the vertices
• directed graph or digraph - {v₁, v₂} - graph in which each edge is associated with an ordered pair of vertices
• undirected graph or graph - graph in which each edge is associated with an unordered pair of vertices
• adjacent - a vertex v₁ in a graph G is adjacent to v₂ if there is an edge between v₁ and v₂
• adjacent - a vertex v₁ in a digraph G is adjacent to v₂ if there is a directed edge from vertex v₁ to vertex v₂
• path - sequence of vertices v₁, v₂, v₃,...v_n where there is an edge from v_i to v_i+1
• simple path - path in which all vertices are distinct
• cycle - a path in which first and last vertices are the same
• simple cycle - a cycle that begins and ends at the same vertex and does not pass through other vertices more than once
• acyclic graph - graph with no cycles
• tree - connected, acyclic graph with a specially designated vertex called the root
• connected graph - there is a path between any two vertices (undirected)
• strongly connected - there is a path between any two vertices (digraph)
• weakly connected - there is a path from vertex I to vertex J or from vertex J to vertex I
• outdegree of a vertex - number of edges extending from the vertex (digraph)
• indegree of a vertex - number of edges entering a vertex (digraph)
• degree of a vertex - number of edges adjacent to a vertex
• complete graph - a graph with each pair of distinct vertices having an edge between them (graph with n vertices and exactly n(n-1)/2 edges)
• complete directed graph - a directed graph with exactly n(n-1) edges
• weighted graph - graph in which the edges represent numeric values
• directed path - sequence of directed edges between two vertices
• multigraph - figure which has multiple occurrences of the same edge (two or more edges between two vertices)
• network - graph in which each edge has an associated positive numerical weight

Graph Algorithms

• 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
• 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 be fore visiting any other vertex
• 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
• topological sort - technique for arranging the vertices into topological order
• spanning tree - a subgraph of a connected undirected graph that contains all of its vertices and enough of its edges to form a tree
• DFS spanning tree - spanning tree created by executing a depth-first search of a graph's vertices
• BFS spanning tree - spanning tree created by executing a breadth-first search of a graph's vertices
• minimum spanning tree - spanning tree of a weighted, connected, undirected graph which has minimal edge-weight sum
• 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
• 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
• Hamilton circuit - a path that begins at a vertex v, passes through every vertex in the graph exactly once, and terminates at v.
• Traveling salesman problem

Last Modified: