Graph Theory

From Wikibooks, open books for an open world
Jump to: navigation, search

Loupe light.svg

Graph Theory is the study of interactions between nodes (vertices) and edges (connections between the vertices), and it relates to topics such as combinatorics, scheduling, and connectivity making it useful to computer science and programming, engineering, networks and relationships, and many other fields of science. Graph theory can be thought of as the "mathematician's connect-the-dots" but it does not examine graphs as done in Calculus (curves and other related concepts).

Table of Chapters

  1. Introduction
  2. Definitions
  3. Degrees and parameters
  4. Algorithms

Simple Tools

  1. Juggling with Binomial Coefficients
  2. Dual Graphs
  3. Star-Delta and Similar Transformations
  4. Hypercubes and Gray Codes Mathematics applied in Computer Science

Degrees and Parameters

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

Special Types of Graphs

  1. k-Connected Graphs
  2. Planar Graphs