離散數(shù)學課件第5章(2)-在線瀏覽
2025-03-05 20:25本頁面
【正文】 22/2/13 Introduction to Graphs 【 Definition】 A simple graph G=(V,E) consists of vertices, V, and edges, E, connecting distinct elements of G=(V,E)是由非空頂點集 V和邊集 E所組成的， V的不同元素的無序?qū)ΨQ為邊。 For example, a b c d a b c d a b c d 16 2022/2/13 Introduction to Graphs The relations of different undirected graphs 各種無向圖之間的關(guān)系 Pseudographs 偽圖 Multigraphs 多重圖 Simple Graphs 簡單圖 17 2022/2/13 Directed Graph: In a directed graph有向圖 G = (V, E) the edges are ordered pairs （有序?qū)Γ?of (not necessarily distinct) (V,E)是由非空頂點集 V、邊集 E所組成的，邊 V中元素的有序?qū)Α? In a directed multigraph 有向多重圖 G = (V, E) the edges are ordered pairs of (not necessarily distinct) vertices, and in addition there may be multiple edges. 有向多重圖G=(V,E)是由非空頂點集 V、邊集 E以及從 E到 {(u,v)|u,v∈ V}的函數(shù) f所組成的。 Introduction to Graphs 12( ) ( )f e f e?18 2022/2/13 Introduction to Graphs Types of Graphs and Their Properties圖的類型及其性質(zhì) 類型 Type 邊 Edges 允許多重邊 Multiple Edges? 允許環(huán) Loops? simple graph 簡單圖 Undirected 無向 No 否 No 否 Multigraph 多重圖 Undirected 無向 Yes 是 No 否 Pseudograph 偽圖 Undirected 無向 Yes 是 Yes 是 directed graph 有向圖 directed 有向 no 否 Yes 是 dir. Multigraph 有向多重圖 Directed 有向 Yes 是 Yes 是 19 2022/2/13 Introduction to Graphs Graph Models圖模型 見教材 p447 20 CHAPTER 5 Graphs Introduction to Graphs 圖的概述 Graph Terminology 圖的術(shù)語 Representing Graphs and Graph Isomorphism圖的表示和圖的同構(gòu) Connectivity 連通性 Euler and Hamilton Paths 歐拉通路和哈密頓通路 Planar Graphs and Graph Coloring 平面圖與著色 Trees 樹 21 2022/2/13 Graph Terminology Basic Terminology基本術(shù)語 Undirected Graphs G=(V, E)無向圖 ? Vertex, edge ? Two vertices, u and v in an undirected graph G are called adjacent (or neighbors) in G, if {u, v} is an edge of G. 若 {u,v}是無向圖 G的邊，則兩個頂點 u和 v稱為在 G里鄰接 (或相鄰 )。 Notation: deg(v) ? If deg(v) = 0, v is called
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1