复旦大学：《离散数学》PPT教学课件（赵一鸣）13/28

1期中测验时间和地点: 11月4日,上午94011:40 地点:教室 2答疑时间和地点: 1)|月1日(周五)3:0015:00软件楼319 2)1月2日和3日,14:00-17:00软件楼3楼 机房讨论室

1.期中测验时间和地点： 11月4日,上午9:40—11：40 地点： 教室 2.答疑时间和地点： 1)11月1日(周五)13:00—15:00 软件楼319 2)11月2日和3日，14:00—17:00 软件楼3楼 机房讨论室

Definition 15: A graph is called connectivity if there is a path between every pair of distinct vertices of the graph. Otherwise, the graph is disconnected &A graph that is not connected is the union of two or more connected subgraphS, each pair of which has no vertex in common. These disjoint connected subgraphs are called the connected components of the graph

❖ Definition 15: A graph is called connectivity if there is a path between every pair of distinct vertices of the graph. Otherwise , the graph is disconnected. ❖ A graph that is not connected is the union of two or more connected subgraphs, each pair of which has no vertex in common. These disjoint connected subgraphs are called the connected components of the graph

8 Example: Let G be a simple graph. If G has n vertices, e edges, and o connected components then n-≤e≤(n-)n-O+1) Proof: e>n-o Let us apply induction on the number of edges of G. e=0, isolated vertex, has n components, n=o 0=e>n-0=0, the result holds Suppose that result holds for e=eo-1 Omitting any edge (G has n vertices, o components and eo-1 edges. (2)G has n vertices, @+1 components and eo-1 edges

❖ Example: Let G be a simple graph. If G has n vertices, e edges, and ω connected components , then ( )( 1) 2 1 n −  e  n − n − + Proof: e≥n-ω Let us apply induction on the number of edges of G. e=0, isolated vertex，has n components ，n=ω, 0=e≥n-ω=0，the result holds Suppose that result holds for e=e0 -1 e=e0 , Omitting any edge , G', (1)G' has n vertices, ω components and e0 -1 edges. (2)G' has n vertices, ω+1 components and e0 -1 edges

e≤(n-0)(n-O+1) 令LetG1,G2,…, Gobe o components of G.G;has vertices for i==1,2,…,o,andn1+n2+…+non and e;<-n,(n (n-O)(n-)+1), 2 The complete graph on n-O+l vertices and o-1 isolated vertices

( )( 1) 2 1 2. e  n − n − + ❖ Let G1 ,G2 ,…,Gωbe ω components of G. Gi has ni vertices for i=1,2,…, ω, and n1+n2+…+nω=n ，and ( 1) 2 1 ei  ni ni − ( )( 1) 2 1 n − n − + ， The complete graph on n-ω+1 vertices and ω-1 isolated vertices

If G is connected, then the number of edges of G has at least n-1 edges ree

If G is connected, then the number of edges of G has at least n-1 edges. Tree

5.2.3 Connectivity in directed graphs .o Definition 16: Let n be a nonnegative integer and g be a directed graph. A path of length n from u to v in G is a sequence of edges ere2y-.en of G such that e=(vo=u, v1),e2=(v1v2 en=(vn1 vn=v), and no edge occurs more than once in the edge sequence. A path is called simple if no vertex appear more than once A circuit is a path that begins and ends with the same vertex. A circuit is simple if the vertices vo, V1,.Vn are all distinct

❖5.2.3 Connectivity in directed graphs ❖ Definition 16: Let n be a nonnegative integer and G be a directed graph. A path of length n from u to v in G is a sequence of edges e1 ,e2 ,…,en of G such that e1=(v0=u,v1 ), e2=(v1 ,v2 ), …, en=(vn-1 ,vn=v), and no edge occurs more than once in the edge sequence. A path is called simple if no vertex appear more than once. A circuit is a path that begins and ends with the same vertex. A circuit is simple if the vertices v0 ,v1 ,…,vn are all distinct

e10 e (el,e2,e7,el, e2, e7)is not a e 9 circuit )音g2 (el, e2, e7, e6, e12)is a c circuit e e e7 circuit:(a, b, c e4 (el,e2, e7)is a simple a) d e5 &(e1, e2, e7, e1, e2, e9)is not a path oo(e1, e2, e7, e6, e9)is a path from a to e oo(e1, e2, e9)is a path from a to e, is a simple path oo(a, b, c e

❖ (e1,e2,e7,e1,e2,e9)is not a path ❖ (e1,e2,e7,e6,e9)is a path from a to e ❖ (e1,e2,e9)is a path from a to e, is a simple path. ❖ (a,b,c,e) (e1,e2,e7,e1,e2,e7)is not a circuit (e1,e2,e7,e6,e12) is a circuit (e1,e2,e7) is a simple circuit. (a,b,c,a)

4 Definition 17: A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph. A directed graph is connected directed graph if there is a path from a to b or b to a whenever a and b are vertices in the graph. A directed graph is weakly connected if there is a path between every pair vertices in the underlying undirected graph

❖ Definition 17: A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph. A directed graph is connected directed graph if there is a path from a to b or b to a whenever a and b are vertices in the graph. A directed graph is weakly connected if there is a path between every pair vertices in the underlying undirected graph

2v4 中定策 聊中市回 使个原十 12 8(strongly connected %(b)connected directed '(weakly connected 令 strongly connected components:G1,G2…,Go

❖ (a)strongly connected ❖ (b)connected directed ❖ (c)weakly connected ❖ strongly connected components: G1 ,G2 ,…,Gω

G(V1) G(V2) G(V3) UA U U6 U5 (b)的路径 令V={v1,V2V3,V42V5,V6,V7,v 令V1={v172V8},V2={v2,v3,v5,v6},V={4, strongly connected components 令G(V1,G(V2),G(V)

❖ V ={v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7 , v8 } ❖ V1={v1 ,v7 ,v8 }, V2={v2 ,v3 ,v5 ,v6 }, V3={v4 }, ❖ strongly connected components : ❖ G(V1 ),G(V2 ),G(V3 )