Basics Of Graph Theory

Graphs

Nitin Upadhyay February 24, 2006

Discussion 

What is a Graph?



Applications of Graphs



Categorization



Terminology

What is a Graph? A graph G=(V,E) consists of a finite nonempty set V, the elements of which are the vertices of G, and a finite set E of unordered pairs of distinct elements of V called edges. G = ( V, E ) Where, V - set of vertices E - set of edges

V = {1, 2, 3, 4, 5}

3

1 Edge

4

E = { (1,2), (1,3), (1,4), (2,3), (3,5), (4,5) }

Vertex (Node)

2 5

Graph applications 

Graphs can be used for:           

Finding a route to drive from one city to another Finding connecting flights from one city to another Determining least-cost highway connections Designing optimal connections on a computer chip Implementing automata Implementing compilers Doing garbage collection Representing family histories Doing similarity testing (e.g. for a dating service) Pert charts Playing games

Graph applications 

Computer

Computer Networks

Resistor/Inductor/…



Electrical Circuits



Road Map City

Graph Models      



Acquaintanceship Graphs – showing whether two people know each other, that is, whether they are acquainted. Influence Graphs – showing whether a person can influence another (e.g., a  b) by using a directed graph. The Bollywood Graph – showing whether the actors have worked together in a movie. Round-Robin Tournaments – showing if team a beats team b (using an edge (a, b)) via a directed graph. Collaboration Graphs – modeling joint authorship of academic papers (an edge links two people if they have jointly written a paper). Call Graphs – modeling telephone calls made in a network (can use either directed multigraphs or undirected ones, depending on the interest) The Web Graph – representing hyperlinks between Web pages using a directed graph. E.g., Web page a links to Web page b via an edge pointing from a to b.

Structure of the Internet SOURCE: CISCO SYSTEMS NAP

Europe

Backbone 1 NAP

Backbone 4, 5, N

Japan Regional A

Backbone 2

NAP

NAP

Backbone 3

Australia

Regional B

MAPS

UUNET MAP

Graph Models 

Where are we right now?

Graph categorization      

Simple Graphs Multigraphs Pseudographs Directed Graphs Directed Multigraphs Weighted Graph

Simple Graphs 

A simple graph G = (V,E) consists of: 



a set V of vertices or nodes (V corresponds to the universe of the relation R), a set E of edges / arcs / links: unordered pairs of distinct elements u, v ∈ V, such that uRv.

Multigraphs 





Like simple graphs, but there may be more than one edge connecting two given nodes. A multigraph G=(V, E, f ) consists of a set V of vertices, a set E of edges (as primitive objects), and a function f from E to Parallel edges {{u,v}| u,v∈V ∧ u≠v}. The edges e1 and e2 are called multiple or parallel edges if f(e1) = f(e2).



E.g., nodes are cities, edges are segments of major highways

Pseudographs 





Like a multigraph, but edges connecting a node to itself are allowed. A pseudograph G=(V, E, f ) where f:E→{{u,v}|u,v∈V}. Edge e∈E is Self loops a loop if f(e)={u,u}={u}. E.g., nodes are campsites in a state park, edges are hiking trails through the woods.

Directed Graphs 





Correspond to arbitrary binary relations R, which need not be symmetric. A directed graph (V,E) consists of a set of vertices V and a binary relation E on V. E.g.: V = people, E={(x,y) | x loves y}

Directed Multigraphs 





Like directed graphs, but there may be more than one arc from a node to another. A directed multigraph G=(V, E, f ) consists of a set V of vertices, a set E of edges, and a function f:E→V×V. E.g., V=web pages, E=hyperlinks. The WWW is a directed multigraph...

Weighted Graph 

A Weighted Graph is a graph where all the edges are assigned weights 50

1 20

3 30

40 2

40

4 30

5

Graph Terminology 

Adjacent, connects, endpoints, degree, initial, terminal, in-degree, out-degree, complete, cycles, wheels, n-cubes, bipartite, subgraph, union.

Adjacency Let G be an undirected graph with vertices u and v, and a linking edge e = {u,v}. Then we say:  u, v are adjacent / neighbors / connected.  Edge e is incident with vertices u and v.  Edge e connects u and v.  Vertices u and v are endpoints of edge e.

Adjacency 



Adjacent vertices: If (i,j) is an edge of the graph, then the nodes i and j are adjacent An edge (i,j) is Incident to vertices i and j 3

1

Vertices 2 and 5 are not adjacent

2 4 5

Degree of a Vertex  

 

Let G be an undirected graph with vertex v. The degree of v, deg(v), is its number of incident edges. (Except that any self-loops are counted twice.) A vertex with degree 0 is isolated. A vertex of degree 1 is pendant.

A Degree Example 

What are the degrees of the vertices in the graphs G and H as shown below? In G, deg(a) = 2, deg(b) = deg(c) = deg(f) = 4, deg(d) = 1, deg(e) = 3 and deg(g) = 0 In H, deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5

a

b

c

d

a

f

e

g

e

c

b

d

Handshaking Theorem 

Let G = (V, E) be an undirected (simple, multi-, or pseudo-) graph with e edges. Then



Corollary: Any undirected graph has an even number of vertices of odd degree.

Handshaking Theorem Example 

How many edges are there in a graph with ten vertices each of degree six? The sum of the degrees of the vertices is 6x10 = 60, it follows that 2e = 60. Therefore, e = 30.

Directed Adjacency 

Let G be a directed (possibly multi-) graph, and let e be an edge of G that is (or maps to) (u,v). Then we say:     

u is adjacent to v, v is adjacent from u e comes from u, e goes to v. e connects u to v, e goes from u to v the initial vertex of e is u the terminal vertex of e is v

Directed Degree 

Let G be a directed graph, v a vertex of G. 





The in-degree of v, deg−(v), is the number of edges going to v. The out-degree of v, deg+(v), is the number of edges coming from v. The degree of v, deg(v)≡deg−(v)+deg+(v), is the sum of v’s in-degree and out-degree.

Directed Handshaking Theorem 

Let G = (V, E) be a directed (possibly multi-) graph with vertex set V and edge set E . Then:



Note that the degree of a node is unchanged by whether we consider its edges to be directed or undirected.

Path  



Path: A sequence of edges in the graph There can be more than one path between two vertices Vertex A is reachable from B if there is a path from A to B G A

Paths from B to D - B, A, D - B, C, D -

F

D B C

E

Path 

Simple Path: A path where all the vertices are distinct 3

1 2 4 5

1,4,5,3 is a simple path. But 1,4,5,4 is not a simple path.

Length 

Length : Sum of the lengths of the edges on the path. 3

1

Length of the path 1,4,5,3 is 3

2 4 5

Circuit 

Circuit: A path whose first and last vertices are the same 3

1

The path 3,2,1,4,5,3 is a circuit.

2 4 5

Cycle 

Cycle: A circuit where all the vertices are distinct except for the first (and the last) vertex 3

1

1,4,5,3,1 is a cycle

2

1,4,5,4,1 is not a cycle

4 5

Questions Questions ?