程序代写代做代考 graph algorithm C decision tree Complex Networks: Lecture 3a: Introduction to Graph Theory

Complex Networks: Lecture 3a: Introduction to Graph Theory
EE 6605
Instructor: G Ron Chen
Most pictures on this ppt were taken from un-copyrighted websites on the web with thanks

What is a
Graph?

A graph is a diagrammatical representation of some physical structure
such as:
a circuit
a computer network
a human relationship network … and so on.

Beginning of Graph Theory
Euler (1707-1783) proved that the Königsburg seven-bridge problem has no solution

Notation


Examples of General (non-simple) Graphs
52 1
weighted graphs
sometimes considered
graph with self-loop or multiple edges
are not allowed
not allowed
Convention:
When a node is removed, all its edges will also be removed

Hyper-Graph
 Concept: A generalization of a graph, where an edges can connect any number of nodes.
 Formally, a hypergraph H is a pair H = (X,E) where X is a set of nodes {v} and E is a set of subsets {e} of X (called hyper-edges).
Hyper-graphs are not simple graphs

Examples of Simple Graphs B
A

CD
N(G)A,B,C,D M(E)AB,AC,BC,CD
A simple graph with 3 components


N  K  M  12 ( N  K ) ( N  K  1 ) N  1  M  12 N ( N  1 )
Examples:
N-1
A graph of N nodes has N(N-1)/2 edges
1

Corollary: If a simple graph of N nodes satisfies
M  12  N  1   N  2 
Proof.Ifnotconnected,thenK2in NKM12(NK)(NK1) In case of K = 2: N  2  M  12 (N 1)(N  2)
But, now it is assumed M  12 N 1 N  2
This is a contradiction.
then it must be connected.
Examples:

Some Basic Results
 Theorem (Handshaking Lemma) The total node degree of a graph is always an even number.
 Proof. Since every edge joins two nodes, so the total node degree is twice of the number of edges.
 Corollary: In any graph, the number of nodes of odd degrees must be even.
Examples:

Isomorphism
 Two graphs G1 and G2 are said to be isomorphic, if there is a one-one correspondence between the nodes of G1 and those of G2 , with the property that the number of edges joining any two nodes of G1 is equal to the number of edges joining the two corresponding nodes of G2 .
 Example:

Graph Isomorphism is a Mapping
bipartite graph
This mapping is one-to-one and onto, hence invertible.

Example

Example

Bipartite Graphs

Bipartite Graphs

Circuits in Bipartite Graphs
 Theorem: A graph is bipartite if and only if every circuit (cycle) has an even number of edges in the path.
 Proof. Let v v v v be a circuit in the bipartite graph 12 n1
G  GV ,V  v V
. Assume, without loss of generality, that 1 1 Then, since G is bipartite, one must have v V ,v V etc.
12
vV 2231 Finally, one must have n 2 in order to form a circuit,
yielding an even number of paths.
Another direction is obvious, since to form a circuit any path has to return to the same side, which has even number of edges.
Circuit = Loop = Circle = Closed Path
V1 V2
.

Tripartite Graphs
Tripartite Graph: All nodes are partitioned into three sets in such a way that no two vertices contained in any one of the three parts are adjacent

Adjacency Matrix
 For a graph G with nodes N (G)  1,2,…, n, its adjacency matrix A is defined to be the n  n constant matrix those ijth entry is 1 if node i connects node j; or 0 otherwise.
 Example: 12
1234 10 1 0 1
21 0 1 1 A0 1 0 1
43
3 41 1 1 0
(always square and symmetrical)
Computer/algorithm uses the adjacency matrix to store a network

Incidence Matrix
 For a graph G with edges M (E)  1,2,…, m, its incidence matrix M is defined to be the n  m constant matrix whose ijth entry is 1 if node i connects edge j ; or 0 otherwise.
 Example:
1 2 21 1 0 0 1
12345
11 0 0 1 0 M0 1 1 0 0
1
43 40 0 1 1 1
5
2
43
(usually non-square)
3

Second-Order Adjacency Matrix
degrees

Clustering Coefficient
1N
Cik(k1) aijajkaki A[aij]
— adjacency matrix
i i j , k 1 ( j  k )
C  1 (a a a )(a a a )(a a a )(a a a )(a a a )(a a a )2
1 3(31)
 16  1  0  0  0  0   2  1 / 3
12 23 31 13 34 41 14 45 51 12 24 41 12 25 51 13 35 51
Average Clustering Coefficient of graph:

Density of Graph

Number of Paths of Length n
number of paths of length 1
number of paths of length 2

Example:
12
Degree matrix
DAL
2 0 0 0 0 1 0 1 2 1 0 1
Laplacian Matrix
Definition: Laplacian matrix (admittance matrix, Kirchhoff matrix), denoted L  L , is defined as
ij
ki if i j
L i j    1 i f i  j , v i a d j a c e n t w i t h v j  0 otherwise
where ki is the degree of node vi
It has zero row-sum (and, by symmetry, zero column-sum)
43
0 0 0 3 1 1 1 0 1 1 1 3 L=D-A
 0 3 0 0 1 0 1 1 1 3 1 1
L    0 0 2 0 0 1 0 1 0 1 2 1

Relationships
3 1 1 0 1
1 3 1 1 0 L1 1 2 0 0 0 1 0 1 0
1 0 0 0 1 

Eigenvalues of Laplacian Matrix
2  0 is called the spectral gap of the graph, or the algebraic connectivity of the network

Verification

eigenvalues of L: 1 1
1 1
3 1 1 0 1
1 3 1 1 0
L1 1 2 0 0
0 1 0 1 0
1 0 0 0 1 
symmetrical with zero row-sum
0 5 5, 5 13 1 2,3 2 2 4,5 2 2
Examples
eigenvalues L:
02 12

Regular Graphs
 A graph in which all nodes have the same degree is called a regular graph; if every node has degree r then the graph is called a regular graph of degree r (or, r-regular)
 Theorem: A regular graph of degree r with N nodes has r N / 2 edges.
 Proof. Since every node connects with r edges, there are r N connecting edges. However, each edge has been doubly counted, so it should be divided by two.
 Example:
A regular graph of degree 3 (3-regular), which has 6 nodes and 3 x 6 / 2 = 9 edges

Eigenvalues of Regular Graphs
Let G be a connected r-regular graph with N nodes, with eigenvalues  ,  ,…,  ,   of its adjacency matrix A
12 N1N r   r
(i)
(ii) G is bipartite if and only if the above eigenvalues are
1 N1N
symmetrical about 0; and if and only if 1  r r1 2 N1 N r
A0 1 1 0
1  1 12

Line Graphs
Given a graph G, its line graph L(G) is a graph such that i) each node of L(G) represents an edge of G
ii) two nodes of L(G) are adjacent if and only if their corresponding edges share a common node in G
That is, it is the intersection graph of the edges of G, representing each edge by the set of its two end-nodes
There are linear-time algorithms for recognizing line graphs and reconstructing their original graphs

Line Graphs
Graph G Nodes in L(G)
Added edges in L(G) Line graph L(G)

Planar Graphs
 Plane graph is one that can be drawn on the 2D plane without crossing edges
 Planar graph is one that is isomorphic to a plane graph  Every planar graph can be embedded on a 2D plane
(within the Euclidean 3D space)
 Theorem: A graph is planar
if and only if it can be embedded on the surface of a sphere.
Planar Plane

They can be embedding on to a 3-D sphere
Impossible to do so

Non-Planar Graphs
 Two special yet important non-planar graphs:
Graph K5 Graph K3,3
K. Kuratowski
(1896 -1980)

Ramsey Problem
6 people meet in a party
If two persons know each other, then connect them with a red edge
If two persons don’t know each other, then connect them with a blue edge
How many red triangles ? How many blue triangles?

Try one case
1
2
Ramsey Theorem:
There exists at least one red triangle or one blue triangle

3 know each other OR 3 don’t know each other
3?

Homeomorphism
 Two graphs are said to be homeomorphic, if they can both be obtained from the same graph by inserting new nodes of degree-2 into edges.
(namely, identical to within nodes of degree-2)
 Theorem (Kuratowski Theorem) A graph is planar if and only if it contains no subgraphs homeomorphic to K5 or K3,3

An Application Example
Recall: The Königsburg seven-bridge problem
Homeomorphic
With multiple edges
A simple graph

BREAK
10 minutes

More Concepts
 Walk: A finite sequence of edges, one after another, in the form of v v ,v v ,…,v v where N(G)  v ,v ,…,v  are nodes
1223 n1n
 A walk is denoted by v v v and the number of
12n edges in a walk is called its length
 Trail: A walk in which all edges are distinct
 Path: A trail in which all nodes are distinct, except
12n
perhaps v  v which is called a closed path, often 1n
called a circuit (or, a cycle)  Tree: A graph with no circuits

 Lemma: If every node in a graph has degree then this graph contains a circuit (cycle).
 Proof.
Consider a simple graph. Starting from any node v0 ,
construct a walk v  v  v   in such a way that v is 012 1
any adjacent node of v0 and, for i  1,2,…, node vi 1 is any (except vi 1 ) adjacent node of vi . Since every node has degree , such a node vi 1 exists. Because the graph has finitely many nodes, the walk eventually connects to a node that has been chosen before. This walk yields a circuit in the graph.
The converse may not be true:

Trees
 Tree: A connected graph without circuits  Forest: A family of unconnected trees
 A tree with N nodes has N – 1 edges
 Sum of node degrees in a tree
= 2 x (number of edges) = 2 (N – 1)

Family Tree
Chemistry
Decision Tree

Tree-Like Graph

Some Basic Results
Theorem: Let T be a graph with N nodes. Then, the following statements are equivalent:
 T is a tree
 T has N – 1 edges but contains no circuits
 T has N – 1 edges and is connected
 T is connected, but the removal of any edge will disconnect the graph
 every pair of nodes of T are connected by exactly one path
 T contains no circuits, but the addition of any new edge creates exactly one circuit

Fractal Tree Graphs
Number of nodes: N
Number of breaches: d Number of generations: g Number of peripheral nodes: m

Complementary Graph
For a given graph G, its complementary graph Gc is the graph containing all the nodes of G and all
the edges that are not in G
G
Gc

Graph Connectivity
 Q: How many edges or nodes must be removed in order to disconnect an originally connected graph?
 Note: If a node is removed, then all edges joining it will also be removed; but the converse is not so.
Example:

Disconnecting Sets and Cut-Sets
 Disconnectingset:Asetofedges,denotedasE0(G),suchthatafter
it is being removed, the graph G will become unconnected
 Cut-Set: The smallest disconnecting set, i.e., no proper subset of
which is a disconnecting set
 Example: E1(G)e,e E2(G)e,e,e E3(G)e,e,e,e 012012503678
are disconnecting sets, in which both E1 (G) and E3 (G) are cut-sets 00

Bridges
Bridge: A cut-set with only one edge Example: cut-set { e } below is a bridge
e
Bridge is also called Edge Connectivity

Importance of bridges
In a network, a node of low degree may be more important than a node of high degree. For example, on a bridge:

Node Connectivity
Node Connectivity, NC(G), of a connected graph G is the minimum number of nodes whose removal disconnects G
When NC(G) ≥ k, the graph is said to be k-connected
NC(G) = 1 NC(G) = 2 1-connected 2-connected
NC(G) = ?

Edge Connectivity
Edge Connectivity, EC(G), of a connected graph G is the minimum number of edges whose removal disconnects G
Let MD(G) be the minimum node degree of a graph Theorem: NC(G)  EC(G)  MD(G)
NC(G) = 1 EC(G) = 1 MD(G) = 2

Closeness
A node is considered to be more important if it is “closer” to all other nodes. For node vi in a network of N nodes:
 N  1 Closeness: C(vi )  d(v ,v )
Normalization:
C n ( v i )  C ( v i )  ( N  1)
C(yellow) = 1 / (1 + 2) = 1 / 3
C(red) = 1 / (1 + 1 ) = 1 / 2 ( > 1 / 3)
ij j1

Closeness
Distance Closeness normalized
0 1 111 111
1 0 222 222
1 2 022 222 1 2 202 222 1 2 220 222 1 2 222 022 1 2 222 202 1 2 222 220
.143 1.00 .077 .538 .077 .538 .077 .538 .077 .538 .077 .538 .077 .538 .077 .538
Distance Closeness normalized
0 1 2 3 4 4 3 2 1 10 123 4432 21 012 3443 32 101 2344 43 210 1234 44 321 0123 34 432 1012 23 443 2101 12 344 3210
.050 .400 .050 .400 .050 .400 .050 .400 .050 .400 .050 .400 .050 .400 .050 .400 .050 .400

Graph-Theoretic Centre
Also called Barry Centre or Jordan Centre
The set of all nodes, A, satisfying that the longest distance
d(A,B) to other nodes B, is minimal (or, 1 / d(A,B) is maximal)
All nodes

A
Girth of a Node
Girth of Node A = length of the shortest cycle in the graph,
which passes Node A
AAAA
A
A

Cyclic Coefficient
1
256
34

Example: Node 5
The graph:

Graphical Meaning:
Node 3: Path 312 has 1 ordered adjacent edge 1 out of 4 = 1/4 Node 1: Path 124 has 1 and 134 has 11+1=2 2 out of 4 = 1/2

More about Trees
 Spanning tree of a graph G is a subgraph that is a tree
and it connects all nodes of G
 Spanning tree usually is not unique
For example Two spanning trees of a graph
A
B
E
CD A
B
E
CD

Some Results
Theorem: Let T be any spanning tree of graph G. Then
1) every cut-set of G has an edge in common with T
2) every circuit of G has an edge in common with the complementary graph of T
Spanning tree
Cut-set
(2 edges)
Complementary graph
(lower part)

Eigenvalues of Spanning Trees
Let L be the Laplacian matrix of a connected graph G of size N, with eigenvalues
0   12N
Let L(i, j) be the matrix obtained from L by deleting its i row and j column. Then, the number of spanning trees, n , in G, satisfies
n  det[L(i, j)]  23 N N
Example:
L1 1 02 111 2
n=1

Minimum Connector Problem
 Minimum connector problem: Suppose that one wants to build a highway network connecting N given cities, in such a way that a car can travel from any city to any other city, but the total mileage of the highways is minimum.
 Clearly, the graph formed by taking the N cities as nodes and the connecting highways as edges must be a tree.
2
6
8 5
7
C
A
6
E 8
D
 The problem is to find an efficient algorithm to decide which tree connecting these cities reaches the minimum total mileage.
3
B
4
9

Greedy Algorithm
 Theorem (Kruskal Greedy Algorithm) Let G be a connected graph with N nodes. Then, the following constructive scheme yields a solution to the minimum connector problem:
 let e1 be an edge of G with the smallest weight;
 choose e2 ,…, eN 1 one by one, by choosing an edge ei (not previously chosen) with a smallest weight, subject to the condition that it forms no circuit with all the previous edges {e ,…,e } ;
1 i1
 repeat this procedure until no more edge can be
chosen
 the resulting graph is a spanning tree, i.e., the subgraph of G with edges{e ,…,e }
It is a minimum spanning tree (usually not unique)
1 N1

Method 1
Staring from the shortest edge, apply the greedy algorithm 
Keep the edge
A
2
6
8 5
7
C
4
6
E 8
D
B
3
9

Method 1
Continue the greedy algorithm  A
B
2
6
8 5
7
C
4
6
E 8
D
3
9

Method 1
Continue the greedy algorithm  A
B
2
6
8 5
7
C
4
6
E 8
D
3
9

Because BD = 5 or AE = 6 or BE= 6 will form a circuit
B
7
C
A
6
E 8
D
Method 1
Continue the greedy algorithm 
2
6
8 5
4
3
9

No more edge can be added
2
6 B
A
6
Result
The greedy algorithm finally yields:
4 8
E
5 73
C9D
8

Method 2
Staring from the longest edge, apply the greedy algorithm  Remove the edge to break loop
2
6
8 5
7
C
A
6
E 8
D
B
4
3
9

Method 2
Staring from the longest edge, apply the greedy algorithm  Remove the edge to break loop
2
6
8 5
7
C
A
6
E 8
D
B
4
3

Method 2
Staring from the longest edge, apply the greedy algorithm  Remove the edge to break loop
B
2
6
8 5
7
C
A
6
4
E 3
D

Method 2
Staring from the longest edge, apply the greedy algorithm  Remove the edge to break loop
2
5 7
C
A
6
B
6
4
E 3
D

Method 2
Staring from the longest edge, apply the greedy algorithm  Remove the edge to break loop
B
2
5 7
C
A
6
4
E 3
D

Method 2
Staring from the longest edge, apply the greedy algorithm  Remove the edge to break loop
A 2
B
5 7
C
4
E 3
D

Method 2
Staring from the longest edge, apply the greedy algorithm  Remove the edge to break loop
A 2
B
7
C
4
E 3
D

Result
The greedy algorithm finally yields: A
2
6 B
6
4 8
E
5 73
C9D
8
No more edge can be removed

End