Fundamentals.html (3390B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.1.1 (456663)"/><meta name="keywords" content="ng"/><meta name="altitude" content="-0.7322385907173157"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:00:08 +0000"/><meta name="latitude" content="52.33452599663043"/><meta name="longitude" content="4.86676147773762"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 18:38:18 +0000"/><title>Fundamentals</title></head><body><div><span style="font-weight: bold;">Basic definition</span></div><div>Graph G: consists of V(G) set of vertices and E(G) set of edges</div><div>Edge: consists of vertices u and v, denoted by (u, v)</div><div><br/></div><div>For vertex u ∈ V(G), neighbour set N(u) is set of vertices adjacent to u</div><div><br/></div><div>Simple graph: does not have multiple edges between pairs, or loops</div><div>Bipartite graph: where you can partition vertices into two subsets, with no edge incident to vertices from same subset </div><div>Tree: graph that has no cycles </div><div>Degree δ(v): number of edges on node, loops are counted twice.</div><div>Degree sequence: list of all vertices’ degrees in a graph. Ordered if it’s in descending order</div><div><br/></div><div>Handshaking lemma: sum of degrees of all vertices in a graph is twice the number of edges in the graph</div><div><br/></div><div><span style="font-weight: bold;">Traversal definitions</span></div><div>Least to most strict:</div><ul><li><div>walk: a sequence of vertices and edges (closed or open)</div></li><li><div>trail: a walk with no repeating edges (open)</div></li><li><div>tour: a walk with no repeating edges, start=end (closed)</div></li><li><div>path: a walk with no repeating vertices or edges (open)</div></li><li><div>cycle: a walk with no repeating vertices or edges, start=end (closed)</div></li></ul><div><br/></div><div>for digraphs, everything’s the same, just directed.</div><div><br/></div><div><span style="font-weight: bold;">Degree sequence</span></div><div>Sequence of numbers is graphic if it’s a degree sequence of a simple graph (could also have other non-simple)</div><div><br/></div><div>Show that a sequence is graphic — Havel-Hakimi theorem:</div><ul><li><div>Given sequence: (1, 2, 1, 3, 3, 2, 3, 5)</div></li><li><div>Order it descending: (5, 3, 3, 3, 2, 2, 1, 1)</div></li><li><div>Systematically remove vertices from start, subtract one from the rest:</div></li><ol><li><div>(2, 2, 2, 1, 1, 1, 1) — remove ‘5', subtract 1 from the next 5 elements</div></li><li><div>(1, 1, 1, 1, 1, 1) — remove ‘2', subtract 1 from the next 2 elements'</div></li><li><div>(1, 1, 1, 1, 0) — remove ‘1', subtract 1 from the next 1 element, reorder</div></li><li><div>(1, 1, 0, 0) — remove ‘1', subtract 1 from the next 1 element, reorder</div></li><li><div>(0, 0, 0) — remove ‘1', subtract 1 from the next 1 element, reorder</div></li><li><div>All ‘0', therefore sequence is graphic.</div></li></ol></ul><div><br/></div><div><br/></div><div><br/></div></body></html>