Lecture 18: Introduction to Graphs
The Seven Bridges of Königsberg
Q: Can you find a path to cross all seven bridges, each exactly once? 3
Copyright By PowCoder代写 加微信 powcoder
Q: (Reformulated as a graph problem) Can you find a path in the graph that includes every edge exactly once?
A: Not possible.
Theorem: A (multi)graph has such a path (known as an Euler path) iff
it contains exactly 0 or 2 vertices with an odd degree.
Q: Can a graph have exactly one vertex with an odd degree?
Seven Bridges of Königsberg: Solution
Solution: Build one more bridge to remove 2 odd-degree vertices. 4
𝑢←any odd-degree vertex if no such vertex exists
𝑢←any vertex
while 𝑢 has an edge not taken yet
take that edge (𝑢,𝑣) 𝑢←𝑣
Algorithm:
Seven Bridges of Königsberg: Initial Algorithm
Algorithm:
𝑢←any odd-degree vertex if no such vertex exists
𝑢←any vertex
while 𝑢 has an edge not taken yet
take that edge (𝑢,𝑣) 𝑢←𝑣
Seven Bridges of Königsberg: Initial Algorithm
171 2D6 2D
Au5 BAu5 B 44
𝑢←any odd-degree vertex if no such vertex exists
𝑢←any vertex
while 𝑢 has an edge not taken yet
take that edge (𝑢,𝑣) 𝑢←𝑣
Algorithm:
But, this “algorithm” may get stuck…
Seven Bridges of Königsberg: Algorithm
117 2D 2D6
A𝑢 5 𝑢B A𝑢 5 𝑢B
Algorithm:
1. Algorithm chooses 𝑢 = 𝑢 = A. Finds path 𝑝 = 𝐴𝐷𝐴𝐶𝐴𝐵𝐶.
Get stuck and stops
2.Itthenchooses𝑢=𝑢 =𝐵. Finds cycle 𝑝 = 𝐵𝐷𝐵.
Gets stuck.
2. It then inserts 𝑝 into 1 to create final solution.
𝑢←any odd-degree vertex Find-Path(𝑢)
Hierholzer’s algorithm (1873)
while there are still edges not yet taken 𝑢←any previously seen vertex that
is endpoint of untaken edge Find-Path(𝑢)
insert 𝑝 into existing path at 𝑢
Find-Path(𝑢):
while 𝑢 has an edge not taken yet
take that edge (𝑢,𝑣) 𝑢←𝑣
Graph Applications
transportation
street intersections
communication
fiber optic cables
World Wide Web
hyperlinks
relationships
predator-prey
software systems
function calls
scheduling
precedence constraints
• Because they model “relationships’’, graphs are ubiquitous.
• Instead of solving problems in one application, we focus on
designing algorithms to solve problems in abstract graphs.
• These can then be used in many different application areas!
Traveling Salesman Problem
Q: How to visit all places, and then return to starting point, travelling the shortest possible distance.
Q: (Reformulated as a graph problem)
Given a graph in which edges have weights (lengths), how to find a cycle with minimum total weight that includes all vertices?
A: Don’t know.
Don’t have an algorithm that runs in polynomial time.
(Conjecture is that such an algorithm doesn’t exist.)
This is actually equivalent to the P = NP problem (still open).
Partial COMP Course Dependency Chart
Edges represent prerequisites
1021, 1022P, 1022Q 2011
3021 2012 2611
4021 3632 3111 3031 3511
3712 4411 4451
Q: (Reformulated as a graph problem)
Given a directed graph, find an ordering of the vertices such that for any edge 𝑢 → 𝑣,
𝑢 is ordered before 𝑣, or declare that there is a cycle in the graph.
Web graph.
World Wide Web
Node: web page.
Edge: hyperlink from one page to another (directed).
netscape.com novell.com
timewarner.com
sorpranos.com
Social Networks
Nodes: people.
Edges: relationship between two people
– Can be directed or undirected
Social network graph.
Reference: , http://www.firstmonday.org/issues/issue7_4/krebs
Undirected and Directed Graphs
set of nodes (vertices).
set of edges between pairs of nodes.
There are two different types of graphs: Undirected and Directed
In most cases we assume simple (as opposed to multi) graphs, where there is at most 1 (2) edges between the same pair of nodes in undirected (directed) graphs.
Undirected graph Directed graph
set of nodes (vertices).
set of edges between pairs of nodes.
Abusing notation, we also use and to denote the number of nodes
and edges. We sometimes also use
Undirected graphs
Edges have no specified “direction”
Undirected Graphs
# edges touching
set of nodes (vertices).
set of edges between pairs of nodes.
Abusing notation, we also use and to denote the number of nodes and edges. We sometimes also use , .
Directed Graphs
Directed graphs.
Edges have directions
If an edge exists in both directions, we will represent it using 2 edges in opposite directions
Outdegree: Indegree:
# edges leaving # edges entering
; 1 2 3 .
Each node connects to |V|-1 other nodes. Therefore the maximum number of edges is |V|(|V|-1)
Exercise on Number of Edges
What is the maximum number of edges in a directed graph G with |V| nodes?
What is the maximum number of edges in a undirected graph G with |V| nodes?
Based on the previous answer, |V|(|V|-1)/2 because we replace 2 directed edges with an undirected one
Exercises on Node Degree
1. Show that if all nodes in a graph have degree 3, then the number of nodes |V| must be even
We have that the sum of all degrees must be equal to twice the number of edges |E|. Therefore, 3|V|=2|E|. For 3|V| to be even, |V| must be even
2. Assume a graph, where all nodes have an odd degree. Show that |V| must be even
Similar to the previous, but now we do not know the degree of each node. Instead lets say that the degree of node vi is: d(vi)=2ki+1, where ki is an integer (e.g., if d(vi)=1, then ki=0, if d(vi)=3, then ki=1 etc). Then
Since |V| equals the difference of 2 even numbers, it must be also even
|V| |V| |V| |V|
(2k 1)|V|2 i
k 2|E||V|2|E|2 k
Exercise on Hand Shaking
Show that at a party, the number of guests who shake hands an odd number of times is even
We construct the graph G = (V,E) where each guest becomes a node. There is an edge between two vertices if and only if the corresponding guests shake hands at the party
Equivalently, we want to prove that “in every graph, the number of nodes with odd degree is even”.
Let V be the set of vertices with odd degree, and V the set odd even
|V | |Vodd | |Veven | |Vodd | |Veven |
d ( v i ) d ( v i ) d ( v i ) 2 | E | d ( v i ) 2 | E | d ( v i )
i1 i1 i1 i1 i1
The sum of even degrees must be even. Since the sum of odd degrees equals the difference of 2 even numbers, it must be also even. Using the same reasoning as the previous exercise, we have:
of vertices with even degree: Vodd Veven = V and Vodd Veven = . We have
(2k 1)|V
|2 k iseven|V |iseven
More Exercises on Node Degrees Q: In a group of 8 people, some of them shake hands. Is it possible that
everyone shaked hands with a different number of people?
Solution: Everyone had between 0 and 7 handshakes. It is not possible that someone shook hands with everyone and someone else with no one. So, there must be at least 2 people with the same number of handshakes.
Q: In a simple, connected graph on 6 vertices, the degrees of 5 vertices are 1, 2, 3, 4, 5 respectively. What is the degree of the 6 th vertex?
Solution 1: Let us call the 5 vertices with known degree v1, v2, . . . v5, where d(vi) = i. The degree of v6 is unknown. Node v5 is connected by an edge to every node, so the only neighbor of v1 is v5. Node v4 is connected to very node except v1. Therefore the two neighbors of v2 are v5 and v4. For v6, we know that it is connected by an edge to v5 and v4, and not connected to v1 and v2. The same is true for v3. Since the degree of v3 is 3, v3 is connected by an edge to v6, therefore the degree of v6 is 3.
Solution 2: Since the sum of the degrees is even, the missing number has to be odd: 1, 3, or 5. Use the first half of the first solution. For v6, we know that it is connected by an edge to v5 and v4 and not connected to v1 and v2, this rules out the degree being 5 or 1.
Graph Representation: Adjacency List and Adjacency Matrix
Graph Representation 2
Adjacency list.
A node-indexed array of lists.
Adjacency matrix.
A 𝑉 × 𝑉 matrix.
Given node 𝑢, retrieving all neighbors in Θ 𝑉 time
Given 𝑢, 𝑣, checking if (𝑢, 𝑣) is an edge takes 𝑂(1) time.
Space: Θ(𝑉).
Given node
neighbors in
Given checking if an edge takes
, retrieving all time
– Fordirectedgraphs,0≤𝐸≤𝑉(𝑉−1)
Can convert from one to the other in Θ(𝑉) time.
Q: How to represent weights?
Adjacency lists are more commonly used, since most graphs are sparse.
Usually, assume no self-loops and duplicated edges.
– Thus, for undirected graphs, 0 ≤ 𝐸 ≤ 𝑉(𝑉 − 1)/2
Paths and Connectivity
Def. A path in a (directed or undirected) graph is a sequence ofnodes suchthat isanedge.Thelengthof
the path is (i.e., # edges in the path). Def. A path is simple if all nodes are distinct.
Def. An undirected graph is connected if for every pair of nodes 𝑢 and 𝑣, there is a path between 𝑢 and 𝑣.
Theorem: For a connected graph, 𝐸 ≥ 𝑉 − 1.
Def. A cycle is a path 𝑣1,𝑣2,…,𝑣,𝑣𝑘 inwhich𝑣1 =𝑣𝑘,𝑘>2,
Def. A cycle is simple
ifthe first𝑘−1nodes
are all distinct.
1 7 9 11 23
2132 is a simple cycle. 2132542 is a nonsimple cycle.
Exercise on Network Connectivity
Q: Suppose in a wireless network of mobile devices, each device is within communication range with at least other devices (assuming is an even number). Show that all devices are connected.
Reformulate as a graph problem: Let 𝐺 = (𝑉, 𝐸) be an undirected graph in which each node has degree ≥ 𝑛/2. Show that 𝐺 is connected.
Pf: Consider any two nodes 𝑢, 𝑣 ∈ 𝑉. There are two cases:
If edge (𝑢, 𝑣) ∈ 𝐸, then 𝑢 and 𝑣 are connected.
If edge (𝑢, 𝑣) ∉ 𝐸 then 𝑢, 𝑣 must have a common neighbor, say 𝑤, because
– 𝑉 contains 𝑛 − 2 nodes other than 𝑢 and 𝑣.
– 𝑢 and 𝑣 each have ≥ 𝑛/2 neighbors among these 𝑛 − 2 nodes.
Thus, 𝑢 and 𝑣 have at least a common neighbor.
The above argument holds for any two nodes 𝑢, 𝑣, so 𝐺 is connected.
Q: If the threshold 𝑛/2 is changed to 𝑛/2 − 1, does the claim still hold?
Connectivity and Shortest Path
s-t connectivity problem.
Given two nodes and , is there a path from to ?
s-t shortest path problem.
Given two node and , what is the shortest path from to ? Def: The length of the path (in terms of number of edges) is the
distance from to .
The problem can be defined on either an undirected or directed graph. If edges
have weights, the distance is the sum of edge weights in the path.
1 7 9 11 23
• 6 & 1 are connected
• 6 & 9 are not connected
• The shortest path from 6 to 8
(6538) has length 3. Note that longer paths exist
Def. An undirected graph is a tree if it is connected and does not contain a cycle.
Def. An undirected graph is a forest if it does not contain a cycle (i.e., a collection of trees).
Theorem (simpler version of Theorem B.4 in textbook):
Let 𝐺 be an undirected graph. Any two of the following statements imply the third (hence 𝐺 is a tree).
(1) 𝐺 is connected.
(2) 𝐺 does not contain a cycle. (3) 𝐸 = 𝑉 − 1.
Proof: (Omitted)
Rooted tree. Given a tree away from .
, choose a root node
and orient each edge
Rooted Trees
the same tree, rooted at 1
parent of 𝑣
child of 𝑣
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com