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 ?