lecture1introduction(編輯修改稿)
2024-08-13 15:19 本頁面
【文章內(nèi)容簡介】 equence of vertices vi, vi+1, …, vj p ? 2022SDU 15 Graph Basics (Cycle) A cycle is a path p = v0, v1, v2, …, vk with v0 = vk. ? For undirected graph, a simple cycle contains at least 3 edges, that is, k ? 3 and v1, v2, …, vk are distinct. ? For directed graph, a simple cycle contains at least 1 edge, and v1, v2, …, vk are distinct. ? Acyclic graph: A graph with no cycles. ? DAG: Directed acyclic graph. ? 2022SDU 16 Graph Basics (Subgraph) A graph G’ = (V’, E’) is a subgraph of G = (V, E) if V’? V and E’ ? E. ? A graph G’’ = (V’’, E’’) is a vertex induced subgraph of G = (V, E) if V’’? V and E’’ = {(u, v) ? E: u, v ?V’’}. G G’ G’’ ? 2022SDU 17 Graph Basics (Connected) An undirected graph is connected if every pair of vertices is connected by a path (reachable from each other). ? Connected ponent of a graph is a subgraph such that: 1) It is connected。 2) Any other subgraph that contains it as a true subgraph is not connected. ? Any connected, undirected graph G = (V, E) satisfies that | E | ? | V | 1. (Hints: Adding each edge decreases of connected ponents by at most one) A directed graph is strongly connected if every two vertices are reachable from each other. ? Strongly connected ponent of a directed graph is a subgraph such that: 1) It is strongly connected。 2) Any other subgraph that contains it as a true subgraph is not strongly connected. ? 2022SDU 18 Connectedness (exa.) G F Other SCCs? ? 2022SDU 19 Special graphs A plete graph is an undirected graph in which every pair of vertices are adjacent. A bipartite graph is a graph G = (V, E) in which V can be partitioned into two disjoint sets V1 and V2 such that (u, v) ? E implies either u?V1 and v?V1 or u?V2 and v?V2. A forest is an acyclic, undirected graph. A tree is a connected, acyclic, undirected graph. (|E|=|V|1) (proof? Induction on of vertices) ? 2022SDU 20 Sparse vs. Dense Sparse graph: | E | is much less than | V |2 Dense graph: | E | is close to | V |2 ―Spare‖ and ―dense‖ are relative concepts. ? 2022SDU 21 Asymptotic Notation (O) Onotation: Asymptotic upper bound ? O(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ? f(n) ? cg(n) for all n ? n0}. – f(n) = 2n3+3n5 ?(or =) O(n3) – f(n) = 2n3+3n5 ?(or =)O(n4) ? 2022SDU
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1