Transcript Graphs - UF CISE

Graphs
A Graph G = (V, E) consists of V, a nonempty set of vertices
(or nodes) and E, a set of edges. Each edge has either one
or two vertices associated with it, called its endpoints. An
edge is said to connect its endpoints.
Denver
Chicago
LA
No two different edge
connect the same pair
of vertices
Miami
Tampa
A very simple Computer Network : An example of a simple graph
It is also an undirected graph (edges have no direction).
Denver
Chicago
LA
Miami
Tampa
Now each edge has a direction associated to it. The edges are called
directed edges and the graph is called a directed graph.
A directed edge is associated with an ordered pair of vertices (u, v).
The edge is said to start at u and end at v.
Note that e = (u, v) and f = (v, u) are two different directed edges
Denver
Chicago
LA
Miami
There are multiple edges (edges connecting the same pair of vertices).
The graph is not simple and is called (undirected) multigraphs.
Denver
Chicago
LA
Miami
Tampa
There are loops in the graph, and the graph is sometimes called a
pseudograph.
Example: Acquaintanceship Graph
Use graph to represent various relationships between
people.
Helen
Doug
Mary
Charles
John
Edge connecting two people when they know each other.
The graph is undirected with no multiple edges, or loops.
Example: Call Graphs
Use graph to model telephone calls made in a network
(say a long distance telephone network).
352-343-2563
352-343-1453
Vertices are phone numbers.
352-343-6745
Each directed edge (u, v) represents a call
from u to v.
A directed graph
352-343-3424
Example: The Web Graph
The World Wide Web can be modeled as a directed graph.
A vertex represents a web page and a directed edge (u, v)
represents a link on u pointing to v.
Extra Credit Assignment
Cot3100
Homepage
Vertices are web pages.
Slides
Each directed edge (u, v) represents a link on
u pointing to v.
WebCT
A directed graph
Graph Terminology
Two vertices u and v in an undirected graph G are called
adjacent (or neighbors) in G if u and v are endpoints of an
edge of G.
If e is associated with { u, v }, the edge e is called incident
with the vertices u and v. The edge e is also said to connect
u and v, and u and v are endpoints of e.
The degree of a vertex in an undirected graph is the number
of edges incident with it (a loop contributes twice to the
degree of that vertex).
Helen
Doug
Mary
Charles
John
deg ( Mary) = 3, deg(John) = 1, deg(Charles)=2, deg(Doug)= 2 and
deg(Helen) = 2.
The Handshaking Theorem
Let G = (V, E) be an undirected graph with e edges. Then
2e=
Σv
deg(v)
If we add all the degrees (of vertices), each edge will be
counted twice. Hence the result.
Corollary: An undirected graph has an even number of
vertices of odd degree.
2e=
Σv
deg(v) = Σ v:odd deg(v)
+ Σ v:even deg(v)
Helen
Doug
Mary
Charles
John
deg ( Mary) = 3, deg(John) = 1, deg(Charles)=2, deg(Doug)= 2 and
deg(Helen) = 2.
The sum of all degrees is 10
There are 5 edges.
There are two vertices with odd degree.
352-343-1453
In-degree=3
out-degree=2
352-343-2563 in-degree = 3, out-degree=1
352-343-6745 out-degree=4
352-343-3424
out-degree=1,
in-dgree=2
Cycles
n vertices, v1, v2, ….., vn and edges
{ v1, v2 }, …, {vn-1, vn }
b
a
c
g
f
e
{a, b, d }, {c, e, f, g}
K3, 4
d
females, or suppliers
Males, or warehouses
If a is in V1, then, b, d, e must be in V2 (why?)
Then, c is in V1 and there is no inconsistency.
So we can rearrange the graph as follows: