離散數(shù)學(xué)課件第5章(2)(參考版)
2025-01-19 20:25本頁面
【正文】 For example, (1) A Star work is a K1,n bipartite graph. (2) K3,2 ,mnK36 2022/2/13 Graph Terminology Some applications of special types of graphs 〖 Example 3〗 Local Area Networks. 1. Star topology 星形技術(shù) 2. Ring topology 環(huán)形技術(shù) 3. Bus topology 總線型技術(shù) 37 2022/2/13 Graph Terminology Some New Graphs From Old 【 Definition】 G= (V, E) , H= (W, F) ? H is a subgraph 子圖 of G if . EFVW ?? ,? H is a spanning subgraph生成子圖 of G if . EFVW ?? ,For example, K5 subgraph of K5 38 2022/2/13 Graph Terminology The union of G1and G2 圖的并 The union of two simple graphs G1 = ( V1 , E1 ) and G2 = ( V2 , E2 ) is the simple graph with vertex set V = V1 ? V2 and edge set E = E1 ? E2 . Notation: G1 ? G2 For example, G1 G2 G1 ? G2 = K5 本節(jié)內(nèi)容到此結(jié)束 。 Q1 Q2 Q3 0 1 00 01 11 10 000 001 101 100 010 011 111 110 2n32 2022/2/13 Graph Terminology (5) Bipartite Graphs 偶圖（二分圖） A simple graph G is bipartite if V can be partitioned into two disjoint subsets V1 and V2 such that every edge connects a vertex in V1 and a vertex in G的頂點集分成兩個不相交的非空集合 V1和 V2，使得圖里的每一條邊都連接著V1里的一個頂點與 V2里的一個頂點，則 G稱為偶圖 Note: There are no edges which connect vertices in V1 or in V2. For example, 33 2022/2/13 Graph Terminology 〖 Example 1〗 Is C3 bipartite? v1 v2 v3 No. 34 2022/2/13 Graph Terminology 〖 Example 2〗 Is C6 bipartite? Yes. Because we can display C6 like this: v5 v1 v2 v3 v4 v6 v1 v6 v2 v5 v3 v4 35 2022/2/13 Graph Terminology The plete bipartite graph is the simple graph that has its vertex set partitioned into two subsets V1 and V2 with m and n vertices, respectively, and every vertex in V1 is connected to every vertex in V2, denoted by Km,n, where m = | V1 | and n = | V2 |.完全偶圖 是頂點集分成分別含有m和 n個頂點的兩個子集的圖 。 W3 W4 W5 W6 31 2022/2/13 Graph Terminology (4) nCubes Qn (n0) n立方體
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1