Скачать с ютуб CG4 Graphs: Six Characterizations of Trees в хорошем качестве

CG4 Graphs: Six Characterizations of Trees

(1) Trees are connected graphs with no cycles. Five other characterizations of trees are given and proved. (2) There is a unique walk between every two vertices. (3) Connected & Every edge is a bridge. (4) Connected and |E| = |V| -1. (5) No cycles and |E| = |V| - 1. (6) No cycles but if any edge is added, then a cycle is created. Subscribe ‪@Shahriari‬ for in-depth math videos at the undergraduate level. 00:00 Introduction 00:20 Goals 01:39 Definition: Graphs, multigraphs, general graphs (   • CG1 Graphs: Basic Vocabulary  ) 03:18 Definition: Paths, Cycles, Trails, Circuits, Walks (   • CG3 Graph Theory: Walks, Paths, Cycle...  ) 04:21 Lemma: When there is a walk, there is a path 04:50 Definition: Bridge 05:19 Lemma: An edge is a bridge iff it is not on any cycles 06:16 Discussion: How to watch these videos? 06:54 Theorem: In a connected graph, |E| is no less than |V|-1, and if |E| = |V|-1, then all edges are bridges 08:35 Examples of graphs with |E| = |V|-1 08:55 Proof of Theorem 11:50 Lemma: For a simple connected graph, every edge is a bridge iff |E| = |V|-1 12:03 Proof of Lemma 15:15 Definition: Trees, Forests 15:42 Main Theorem: Six Characterizations of Trees 17:15 Strategy for Proof (implication diagram) 18:19 Proof (1) implies (2) 20:12 Proof (2) implies (3) 21:35 Proof (3) is equivalent to (4) and implies (5) 22:48 Corollary: In a tree, every edge is a bridge and |E| = |V|-1 23:22 Proof (5) implies (1) 24:52 Proof (6) implies (1) 26:00 Proof (2) implies (6) 26:45 Recap Next Graph Theory Video:    • CG6 Bipartite Graphs & their Cycles   A series of lectures on graph theory as part of a full course on introductory combinatorics based on my book Shahriar Shahriari, An Invitation to Combinatorics, Cambridge University Press, 2022. DOI: https://doi.org/10.1017/9781108568708 For an annotated list of available videos for Combinatorics see https://pomona.box.com/s/by2ay2872avx... YouTube Playlist:    • Combinatorics, An Invitation   Shahriar Shahriari is the William Polk Russell Professor of Mathematics at Pomona College in Claremont, CA USA