A Vertex of a Graph is a connection point. A Graph has a set of Vertices, usually shown as V = {v1, v2, ..., vn} V = {A, B, C} or V = {1, 2, ... N} The number of Vertices in a graph is |V| but is somtimes written in equations as just V. A Vertex may have no connections, one connection or many connections. A vertex may have any number of properties such as a name or a color.

An Edge in a graph is a connection between vertices. Given vertices v1 and v2 in a Graph, the edge between them may be written as (v1,v2) or sometimes [v1,v2]. A Graph has a set of Edges usually denoted E. E = {(v1,v2), (v2,v3)} The number of Edges in a graph is |E| but is somtimes written in equations as just E. A Graph is called Undirected if the edges have no implied direction. (v1,v2) is the same as (v2,v1), the edge just connects v1 to v2. A Graph is called Directed if the edges have a direction. (v1,v2) means an edge starting at v1 and goint to v2. (v1,v2) is NOT the same as (v2,v1). A Weighted Graph has edges with an additional property, a weight. Weights may be integers, real numbers, gallons per minute or any type of quantity. (v1,v2,10GPM) would indicate an Edge from vertex v1 to v2 with a flow of 10 gallons per minute. There are special cases that may not allow zero or negative weights. An Edge Colored Graph has edges with an additional property, a color. In general, an Edge can have many properties that depend on what the graph represents. (v1,v2,10GPM,green) A general graph may have a self loop which is an edge that goes from a vertex to itself, e.g. (v3,v3). A multi-graph may have more than one edge between the same pair of vertices, e.g. E = {(v1,v2), (v1,v2), (v2,v3)} Note: in a Directed Graph (v1,v2) and (v2,v1) is not a multi-graph, just two edges going different directions. In an Undirected Graph sometimes (v1,v2) and (v2,v1) may be included even though they are redundant and the Graph may not be considered a multi-graph. A cutset (one word) is a set of edges, which when removed, disconnect source vertices from sink vertices. The Edge Connectivity of an Undirected Graph is the minimum number of edges that must be removed to "disconnect the graph." This is a number. A value of zero means the given graph has at least one pair of vertices x, y in V such that there is no path connecting x and y.

A Graph is a set of Vertices and a set of Edges. G = (V, E) There seems to be no standard definition for the properties of a Graph when it is just called a "graph" yet many types of graphs are defined by a sequence of qualifiers: Directed - the edges have a direction, usually drawn with an arrow head at one end. A DAG, Directed Acyclic Graph is a restricted case with no cycles (no loops following direction of edges.) Undirected - usually the default if nothing else said. The edges do not have direction. Acyclic - no cycles, there is no Path that includes at least one edge that can return to the starting vertex. Planar - The Graph can be drawn on a plane (paper, flat surface) with no Edge crossing another Edge. Note: "can be drawn" but it may be drawn with edges crossing. Non planar - A Graph that is impossible to draw on a plane without an Edge crossing. Dense - |E| is close to |V|**2 close is usually not defined precisely but for algorithms it means |E| is O(|V|**2) Connected - There are no unconnected verticies and no isolated groups of vertices. In an Undirected Graph there is a Path from every vertex to every other vertex. Fully connected - every vertex has an edge to every other vertex. Clique - Fully connected component - a subset of the vertices of a Graph that are fully connected. Strongly connected - For a Directed Graph, for every pair of vertices x, y in V a path from x to y implies a path from y to x. (Use DFS to check) Tree - a restricted form of a graph where one vertex is called the root and all verticies have a Path to the root and the graph is undirected and acyclic. Bipartite - a Graph with a set of vertices that can be divided into exactly two non empty subsets such that no edge connects two vertices within a subset and every vertex in one subset has at least one Edge to a vertex in the other subset.

Definition Data Structure Algorithm## Topological Sort of a DAG.

Given a graph G = (V, E) that is directed and acyclic, list the vertices in an order such that for every edge (u,v) u is listed before v. Algorithm: Run DFS on the graph putting finished vertices on the front of the list.

- Automata related definitions
- Formal Language Definitions
- Computability Definitions
- Language Class Definitions

Last updated 1/7/99