Graph Theory

From Wikibooks, the open-content textbooks collection

This book has been created on 3 August 2009, and still is under heavy construction. Content that is added is likely to be moved/deleted/edited significantly in a short amount of time. All wikibookians with knowledge in this subject are welcome to help out. You can remove this tag when the book has become more mature.

This book is intended for advanced readers.

Graph Theory is the study of nodes and the edges connecting those nodes, and topics such as combinatorics, networks, scheduling, and connectivity. Graph theory does not examine graphs as in Calculus (curves and other related concepts). Graph theory can be thought of as the "mathematician's connect-the-dots".

Contents 1 What is Graph Theory? 2 Graph Definitions 3 Degrees and Parameters

[edit] What is Graph Theory?

• Graph Theory (graph theory) is the study of interactions between nodes (vertices) and edges (connections between the vertices).
• There are many applications of graph theory to mathematics, combinatorics, computer science and programming, engineering, networks and relationships, scheduling, and many more.

[edit] Graph Definitions

1. Nodes and Edges
2. Traversals and Paths
3. Connectivity
4. Independence
5. Isomorphic
6. Complement graphs
7. Trees
8. Complete graphs
9. Bipartite graphs
10. New graphs from old ones
11. Types of graphs

[edit] Degrees and Parameters

1. Degree Definitions
2. Theorems using Degrees
3. Regular Graphs
4. Degree Sequences
5. Using matrices to encode graphs