Term | Definition |
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 |
Digraph | {v1, v2} - graph in which each edge is associated with an ordered pair of vertices |
Undirected Graph | graph in which each edge is associated with an unordered pair of vertices |
Adjacent | a vertex v1 in a graph G is adjacent to v2 if there is an edge between v1 to v2 |
Path | sequence of vertices v1, v2, v3,...vn where there is an edge from vi to vi+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 Graph | there is a path between any two vertices (digraph) |
Weakly Connected Graph | there is a path from vertex I to vertex J or from vertex J to vertex I |
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 |
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 |
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 |
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 |
Minimal Spanning Tree | spanning tree of a weighted, connected, undirected graph which has minimal edge-weight sum |
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 | A weighted digraph must be traversed with minimal cost. It is in the set NP; the solution can be guessed and then checked in polynomial time. It is also NPC. |
Four Color Problem | Since the proving of the theorem, efficient algorithms have been found for 4-coloring maps requiring only O(n^2) time, where n is the number of vertices, found in 1996 |
Three Utility Problem | |