lecture1introduction-文庫(kù)吧在線文庫(kù)
【正文】 ? k, the subsequence 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。 ? 《 算法設(shè)計(jì)與分析 》 ：王曉東編著，清華大學(xué)出版社， 30元。 ? 《 計(jì)算機(jī)算法導(dǎo)引 —設(shè)計(jì)與分析 》 ：盧開澄編著，清華大學(xué)出版社， 21元。 ? Element of E: Edge。 Reference Books Text Book: ? Introduction to Algorithms (Second Edition) – Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein – Higher Education Press, The MIT Press, 68RMB Reference Books ? Algorithm Design Techniques and Analysis – . Alsuwaiyel (Saudi Arabia), 電子工業(yè)出版社， 40元。 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號(hào)-1