“mcs”一2018/6/6一13：43-page v一#5 Contents 9.11 RSA Public Key Encryption 378 9.12 What has SAT got to do with it?381 9.13 References 382 10 Directed graphs Partial Orders 421 10.1 Vertex Degrees 423 10.2 Walks and Paths 424 10.3 Adjacency Matrices 427 10.4 Walk Relations 430 10.5 Directed Acyclic Graphs Scheduling 431 10.6 Partial Orders 439 10.7 Representing Partial Orders by Set Containment 442 10.8 Linear Orders 444 10.9 Product Orders 444 10.10 Equivalence Relations 445 10.11 Summary of Relational Properties 447 10.12 References 449 11 Communication Networks 481 11.1 Routing 481 11.2 Routing Measures 482 11.3 Network Designs 485 12 Simple Graphs 501 12.1 Vertex Adjacency and Degrees 501 12.2 Sexual Demographics in America 503 12.3 Some Common Graphs 505 12.4 Isomorphism 507 12.5 Bipartite Graphs Matchings 509 12.6 Coloring 514 12.7 Walks in Simple Graphs 519 12.8 Connectivity 521 12.9 Special Walks and Tours 523 12.10 k-connected Graphs 525 12.11 Forests Trees 527 12.12 References 535 13 Planar Graphs 575 13.1 Drawing Graphs in the Plane 575 13.2 Definitions of Planar Graphs 575 13.3 Euler's Formula 586 13.4 Bounding the Number of Edges in a Planar Graph 587“mcs” — 2018/6/6 — 13:43 — page v — #5 Contentsv 9.11 RSA Public Key Encryption 378 9.12 What has SAT got to do with it? 381 9.13 References 382 10 Directed graphs & Partial Orders 421 10.1 Vertex Degrees 423 10.2 Walks and Paths 424 10.3 Adjacency Matrices 427 10.4 Walk Relations 430 10.5 Directed Acyclic Graphs & Scheduling 431 10.6 Partial Orders 439 10.7 Representing Partial Orders by Set Containment 442 10.8 Linear Orders 444 10.9 Product Orders 444 10.10 Equivalence Relations 445 10.11 Summary of Relational Properties 447 10.12 References 449 11 Communication Networks 481 11.1 Routing 481 11.2 Routing Measures 482 11.3 Network Designs 485 12 Simple Graphs 501 12.1 Vertex Adjacency and Degrees 501 12.2 Sexual Demographics in America 503 12.3 Some Common Graphs 505 12.4 Isomorphism 507 12.5 Bipartite Graphs & Matchings 509 12.6 Coloring 514 12.7 Walks in Simple Graphs 519 12.8 Connectivity 521 12.9 Special Walks and Tours 523 12.10 k-connected Graphs 525 12.11 Forests & Trees 527 12.12 References 535 13 Planar Graphs 575 13.1 Drawing Graphs in the Plane 575 13.2 Definitions of Planar Graphs 575 13.3 Euler’s Formula 586 13.4 Bounding the Number of Edges in a Planar Graph 587