Fundamentals.md (1968B)
1 +++ 2 title = 'Fundamentals' 3 +++ 4 # Fundamentals 5 **Basic definition** 6 Graph G: consists of V(G) set of vertices and E(G) set of edges 7 Edge: consists of vertices u and v, denoted by (u, v) 8 9 For vertex u ∈ V(G), neighbour set N(u) is set of vertices adjacent to u 10 11 Simple graph: does not have multiple edges between pairs, or loops 12 13 Bipartite graph: where you can partition vertices into two subsets, with no edge incident to vertices from same subset 14 15 Tree: graph that has no cycles 16 Degree δ(v): number of edges on node, loops are counted twice. 17 18 Degree sequence: list of all vertices’ degrees in a graph. Ordered if it’s in descending order 19 20 Handshaking lemma: sum of degrees of all vertices in a graph is twice the number of edges in the graph 21 22 **Traversal definitions** 23 Least to most strict: 24 25 - walk: a sequence of vertices and edges (closed or open) 26 - trail: a walk with no repeating edges (open) 27 - tour: a walk with no repeating edges, start=end (closed) 28 - path: a walk with no repeating vertices or edges (open) 29 - cycle: a walk with no repeating vertices or edges, start=end (closed) 30 31 for digraphs, everything’s the same, just directed. 32 33 **Degree sequence** 34 35 Sequence of numbers is graphic if it’s a degree sequence of a simple graph (could also have other non-simple) 36 37 Show that a sequence is graphic — Havel-Hakimi theorem: 38 39 - Given sequence: (1, 2, 1, 3, 3, 2, 3, 5) 40 - Order it descending: (5, 3, 3, 3, 2, 2, 1, 1) 41 - Systematically remove vertices from start, subtract one from the rest: 42 43 1. (2, 2, 2, 1, 1, 1, 1) — remove ‘5', subtract 1 from the next 5 elements 44 2. (1, 1, 1, 1, 1, 1) — remove ‘2', subtract 1 from the next 2 elements' 45 46 3. (1, 1, 1, 1, 0) — remove ‘1', subtract 1 from the next 1 element, reorder 47 48 4. (1, 1, 0, 0) — remove ‘1', subtract 1 from the next 1 element, reorder 49 5. (0, 0, 0) — remove ‘1', subtract 1 from the next 1 element, reorder 50 6. All ‘0', therefore sequence is graphic.