Lecture 2. Graph theory2

Modelingof

ComplexNetworksModeling of Complex Networks

Lecture2: Lecture 2:Introduction to Graph TheoryIntroductiontoGraphTheory

S8101003Q (Sem A, Fall 2014)

Instructor: Aaron, Haijun Zhang,jg

Review

Walk:A finite sequence of edges, one after another, in the form of

v1v2, v2v3,…,vn-1 vn where N(G) = {v1,v2 ,…,vn}are nodes.

A walkis denoted by v1 → v2 → …vnand the number of edges in a

walk is called its length.

Trail: are distinct.

Path:are distinct, except perhaps v1= vnwhich is called a closed path, often called a circuit(or, sometimes, a looppor a cycley)).

Tree:A graph with no circuits.

Eülerian Graphs

edge once and once only. gy

Eülerian Graphs:If it has a

closed trail that traverses each There may be more than one such trail, each of which is Theremaybemorethanonesuchtrail,eachofwhichiscalled an Eülerian trail.

Semi-Eülerian graph: If it has a trail, need not be closed,

that traverses each edge once and once only.

bd336x280();1263_892.83-1080-0-1347-1080.jpg" alt="Lecture 2. Graph theory2" />

Example

Main Results

the degree of every node in the graph is an even number.gygpProof:If a node is a starting point, then the trail has to return to it:Theorem 2-14 A connected graph is Eülerian if and only if If a node has a trail entering it, then the trail has to leave it:g,

Corollary 2-15 The seven-bridge problem of Königsburg has no solutions.pgg

Algorithmto find Eülerian Graphs Corollary 2-16 (Fleury Algorithm) In any given Eülerian graph G, an Eülerian trail can be found by the following procedure:

Start from any node in G. Walk along the edges of Gin an arbitrary manner, subject to the following rules: ¾

¾

¾erase the edges as they are traversed;erasetheresultingisolatednodes;erase the resulting isolated nodes;walk through a bridge only if there are no other alternatives.

bd336x280();1263_892.83-1080-0-1173-1080.jpg" alt="Lecture 2. Graph theory2" />

Example

SirWilliam Rowan Hamilton (1805-1865)

In 1856, the English mathematician William R. Hamilton

studied the world navigation problem and considered a gpmap with 20 nodes representing cities connected by sailing routes, as depicted by the following figure. He wanted to fdfind out if one can traverse through every city once and fhhdonce only, and finally return to the starting city. His study eventuallyledtotheestablishmentofthenow-famous eventually led to the establishment of the now-famousHamiltonian graph theory.

bd336x280();iw=1080-0-1424-1080.jpg" alt="Lecture 2. Graph theory2" />

One Solution ?

Hamiltonian Graphs

once and once only. y

Hamiltonian Graph:If it has a

closed trail that traverses A trivial case is a single node and a nontrivial Hamiltonian ggraph must be a circuit, called a hblldHamiltonian circuit.

Semi-Hamiltonian graph: If it has a trail, need not be

closed, that traverses each node once and once only.

bd336x280();3_892.83-924-0-1126-924.jpg" alt="Lecture 2. Graph theory2" />

Some Results

bd336x280();0_0_0_0_0_1263_892.83-1080-0-1092-1080.jpg" alt="Lecture 2. Graph theory2" />

Shortest Path Length Problem

Q: What is the shortest path length from Ato L ?

Approach to Solving the Shortest Path Length Problem

Moving fromAtowardLand associating each ()that is equal to qintermediate node Vwith a number l(V)the shortest path length from Ato V. For example: from Ato J, one has l(J)=l(G)+5or

l(J)=l(H)+5 whichever is shorter.

Approach to Solving the Shortest Path Length Problem

Starting from Awith l(A)=0, moving from AtowardL, one ()();()();()()hasl(B)=l(A)+3=3; l(E)=L(A)+9=9; l(C)=l(A)+2=2Therefore, nodeBis chosen, with l(B)=3, node Cis chosen, withl(C)=2 and node E is chosen with l(E)=9

Approach to Solving the Shortest Path Length Problem

Looking at the nodes adjacent to B, one hasl(D)=l(B)+2=5; l(E)=L(B)+4=7LookingatthenodesadjacenttoC, one hasLooking at the nodes adjacent toonehasl(E)=l(C)+6=8; l(F)=l(C)+9=11So,l(D)=5 ()is uniquely determined.But l(E)=7, or 8or 9. Hence, node Eis chosen with l(E)=l(B)+4=7Fis chosen withl(F)=11But also ll(F)=l(H)+1. Looking atkl(H)=l(E)+2=9, so Fis chosen with hhl(F)=l(H)+1=10

Approach to Solving the Shortest Path Length Problem

Continuing this way, one obtainsl(A)=0 l(B)=3 l(C)=2 l(D)=5 l(E)=7 l(F)=10l(G)=8l(H)=9l(I)=12l(J)=13l(K)=14l(L)=17l(G)=8 l(H)=9 l(I)=12 l(J)=13 l(K)=14 l(L)=17Final result: total shortest path length =17 from A to L:

SltiSolutions may not be unique, but all will be the shortesttbibtllillbthhtt