lecture1introduction-文庫(kù)吧資料
2025-07-23 15:19本頁(yè)面
【正文】 questions: ? What is a graph? ? How to represent a graph? ? Basic properties of a graph ? 2022SDU 9 Graph Basics (Graph) A graph G is a pair (V, E), where V is a finite set and E is a set of pairs on V ? Denote as G = (V, E) ? Element of V: Vertex。 Undirected graph (u. w. l. g., graph): Each pair in E is unordered, ., for each pair (u, v) ?E, (u, v) = (v, u). Directed graph: Each pair in E is ordered, ., for each pair (u, v) ? E, (u, v) ? (v, u), and either (v, u) ? E or not. G1 = ((1, 2, 3), ((1, 2), (2, 3), (3,1))) G2 = ((1, 2, 3), ((1, 2), (2, 3), (1,4)))? ? 2022SDU 10 Schematic Representation v1 v2 v3 v4 v5 v6 e1 e2 e3 e7 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 Can you give the representation in format G = (V, E) for above? e4 ? 2022SDU 11 Graph Basics (Adjacency) Adjacency: In a graph G = (V, E), if (u, v) ? E, say that vertex v is adjacent to vertex u. ? If G is an undirected graph, vertex u is adjacent to vertex v, too. The adjacency relation is symmetric. We also say (u, v) is incident with u and v, vice versa. ? If G is a directed graph, if (u, v) ? E, vertex v is adjacent to vertex u, vertex u is not necessarily adjacent to vertex v. (u, v) is incident from or leaves vertex u and is incident to or enters vertex v. Two edges are called to be adjacent if they share a mon vertex. ? 2022SDU 12 Graph Basics (Degree) Degree of a vertex v: ? For undirected graph: – Number of edges incident with v. – Denote as dG(v) or simply, d(v). ? For directed graph: – Indegree: Number of edges entering (or incident to) v. – Outdegree: Number of edges leaving (or incident from) v. – Denote as idG(v), odG(v) or simply, id(v), od(v) respectively. ? 2022SDU 13 Graph Properties Theorem (Handshaking Lemma) ? Given an undirected graph G = (V, E), the sum of degrees of all vertices is that , where | E | is the number of edges in G. ? Proof: Can you give? ? How about a directed graph? (sum of indegrees equals to sum of outdegrees, ., the number of edges) Corollary ? Given a graph G = (V, E), the number of vertices with odd degrees is even. ? Proof: Can you give? ( ) 2 | |vV d v E? ??? 2022SDU 14 Graph Basics (Path) A path of length k from a vertex u to a vertex u’ in a graph G = (V, E) is a sequence v0, v1, v2, …, vk of vertices such that u = v0
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1