-
$G( V, E )$ where$G$ = graph,$V = V( G )$ = finite nonempty set of vertices, and$E = E( G )$ = finite set of edges.
-
$( v_i , v_j ) = ( v_j , v_i )$ = the same edge.
- Self loop is illegal.
- Multigraph is not considered.
- A graph that has the maximum number of edges.
- Path(
$\subset G$ ) from$v_p$ to$v_q$ =${v_p,v_{i1},v_{i2},\cdots,v_{in},v_q}$ such that$(v_p,v_{i1}),(v_{i1},v_{i2}),\cdots,(v_{in},v_q)$ belong to$E(G)$
- number of edges on the path
-
$v_{i1},v_{i2},\cdots,v_{in}$ are distinct.
- simple path with
$v_p=v_q$
-
$v_i$ and$v_j$ in an undirected$G$ are connected if there is a path from$v_i$ to$v_j$ (and hence there is also a path from$v_j$ to$v_i$ ) - An undirected graph
$G$ is connected if every pair of distinct$v_i$ and$v_j$ are connected
- the maximal connected subgraph
- a graph that is connected and acyclic(非循环的)
- a directed acyclic graph
- For every pair of
$v_i$ and$v_j$ in$V( G )$ , there exist directed paths from$v_i$ to$v_j$ and from$v_j$ to$v_i$ . - If the graph is connected without direction to the edges, then it is said to be weakly connected
- the maximal subgraph that is strongly connected
-
number of edges incident to v
-
For a directed G, we have in-degree and out-degree.
-
Given G with
$n$ vertices and$e$ edges, then $$ e=(\sum_{i=0}^{n-1}d_i)/2\quad where\quad d_i=degree(v_i) $$
Note : If G is undirected, then adj_mat[][] is symmetric. Thus we can save space by storing only half of the matrix.
-
This representation wastes space if the graph has a lot of vertices but very few edges.
-
To find out whether or not
$G$ is connected, we’ll have to examine all edges. In this case$T$ and$S$ are both$O( n^2 )$ .
- Replace each row by a linked list
Note : The order of nodes in each list does not matter.
- For undirected
$G$ ,$S$ =$n$ heads +$2e$ nodes =$(n+2e)$ ptrs +$2e$ ints - Degree(i) = number of nodes in graph[i](if
$G$ is undirected) -
$T$ of examine$E(G)$ =$O(n+e)$
- Sometimes we need to mark the edge after examine it, and then find the next edge.
- adj_mat [ i ] [ j ] = weight
- adjacency lists / multilists : add a weight field to the node
- digraph
$G$ in which$V( G )$ represents activities and$E( G )$ represents precedence relations - Feasible AOV network must be a directed acyclic graph.
-
$i$ is a predecessor of$j$ = there is a path from$i$ to$j$ -
$i$ is an immediate predecessor of$j$ =$< i, j > \in E( G )$ . Then$j$ is called a successor(immediate successor) of$i$
- a precedence relation which is both transitive and irreflexive
Note : If the precedence relation is reflexive, then there must be an
$i$ such that$i$ is a predecessor of$i$ . That is,$i$ must be done before$i$ is started. Therefore if a project is feasible, it must be irreflexive.
[Definition] A topological order is a linear ordering of the vertices of a graph such that, for any two vertices, $i$ , $j$ , if $i$ is a predecessor of $j$ in the network then $i$ precedes $j$ in the linear ordering.
Note : The topological orders may not be unique for a network.
/*Test an AOV for feasibility, and generate a topological order if possible*/
void Topsort( Graph G )
{
int Counter;
Vertex V, W;
for ( Counter = 0; Counter < NumVertex; Counter++ )
{
V = FindNewVertexOfDegreeZero( );
if ( V == NotAVertex )
{
Error ( “Graph has a cycle” );
break;
}
TopNum[ V ] = Counter; /* or output V */
for ( each W adjacent to V )
Indegree[ W ]––;
}
}/*Improvment:Keep all the unassigned vertices of degree 0 in a special box (queue or stack)*/
void Topsort( Graph G )
{
Queue Q;
int Counter = 0;
Vertex V, W;
Q = CreateQueue( NumVertex );
MakeEmpty( Q );
for ( each vertex V )
if ( Indegree[ V ] == 0 ) Enqueue( V, Q );
while ( !IsEmpty( Q ) )
{
V = Dequeue( Q );
TopNum[ V ] = ++Counter; /* assign next */
for ( each W adjacent to V )
if (––Indegree[ W ] == 0 ) Enqueue( W, Q );
} /* end-while */
if ( Counter != NumVertex )
Error( “Graph has a cycle” );
DisposeQueue( Q ); /* free memory */
}