Mathematics for Computer Science
11 Simple Graphs Simple graphsmodel relationships that aresymmetric, meaning that the relationship is mutual. Examples of such m ...
Chapter 11 Simple Graphs394 graph only has an undirected edge,hv—wi, that connectsvandw. Definition 11.1.1.Asimple graph,G, cons ...
11.2. Sexual Demographics in America 395 does not need to have any edges at all. jE.G/jcould be zero, implying that the degree o ...
Chapter 11 Simple Graphs396 M F Figure 11.2 The sex partners graph. of theFvertices equals the number of edges. So these sums ar ...
11.3. Some Common Graphs 397 partnership, but there are fewer males, so they have a higher ratio. This means that the University ...
Chapter 11 Simple Graphs398 Figure 11.3 K 5 : the complete graph on 5 nodes. Figure 11.4 An empty graph with 5 nodes. Ann-node g ...
11.4. Isomorphism 399 Figure 11.6 C 5 : a 5-node cycle graph. b c a d (a) 2 3 1 4 (b) Figure 11.7 Two Isomorphic graphs. 11.4 Is ...
Chapter 11 Simple Graphs400 Figure 11.8 IsomorphicC 5 graphs. Here is an isomorphism,f, between the two graphs in Figure 11.7: f ...
11.5. Bipartite Graphs & Matchings 401 isomorphic that isguaranteedto run in polynomial time on all pairs of graphs.^3 Havin ...
Chapter 11 Simple Graphs402 Chuck Tom Michael John Alice Martha Sara Jane Mergatroid Figure 11.9 A graph where an edge between a ...
11.5. Bipartite Graphs & Matchings 403 Chuck Tom Michael John Alice Martha Sara Jane Mergatroid Figure 11.10 One possible ma ...
Chapter 11 Simple Graphs404 Inductive Step: Suppose thatjMjDmC 1 2. To find a matching forM, there are two cases. Case 1: Ever ...
11.5. Bipartite Graphs & Matchings 405 neighborsof some setSof vertices is the image ofSunder the edge-relation, that is, N. ...
Chapter 11 Simple Graphs406 It follows thatdjN.S/j djSj. Cancellingdcompletes the derivation of equa- tion (11.2). Regular gr ...
11.6. The Stable Marriage Problem 407 Brad Billy Bob Jennifer Angelina 1 2 2 1 1 2 2 1 Figure 11.11 Preferences for four people. ...
Chapter 11 Simple Graphs408 11.6.1 The Mating Ritual The procedure for finding a stable matching can be described in a memorable ...
11.6. The Stable Marriage Problem 409 Mating Ritual at Akamai The Internet infrastructure company Akamai, cofounded by Tom Leigh ...
Chapter 11 Simple Graphs410 and it is. Definition 11.6.2.LetPbe the predicate: for every woman,w, and man,m, ifw is crossed offm ...
11.6. The Stable Marriage Problem 411 11.6.4... Especially the Men Who is favored by the Mating Ritual, the men or the women? Th ...
Chapter 11 Simple Graphs412 Definition 11.6.9.A person’soptimal spouseis their most preferred feasible spouse. A person’spessima ...
«
16
17
18
19
20
21
22
23
24
25
»
Free download pdf