Field:Graph Theory

From Math Images
Jump to: navigation, search

Graph Theory

Graph theory is the study of graphs. A graph is informally a collection of points, known as vertices, connected by lines, known as edges.

For a more in depth but general discussion, look at the Graph Theory page.


Basic Terminology

  • Acyclic graph- a graph which contains no cycles
  • Adjacent - two vertices are said to be adjacent if an edge connects them.
  • Cycle- A path for which the first element is the same as the final element
  • Directed graph (or digraph)- a graph for which all edges are assigned a direction. That is, for an edge between an arbitrary vertex A and vertex B, assigning a direction means the edge is either directed towards vertex A or towards vertex B.
  • Eulerian Circuit- A cycle which contains all of the edges of a graph. This idea was inspired by the the Seven Bridges of Königsberg problem.
  • Hamiltonian Cycle- A cycle which contains all of a graph's vertices.
  • Hamiltonian Path - A path which contains all of a graph's vertices.
  • Path - A sequence of distinct graph edges
  • Planar Graph - A graph that can be drawn such that no two edges overlap each other.
  • Spanning Tree- a tree which contains all vertices of a graph.
  • Tree- a connected, acyclic graph.
  • Vertex Degree - the number of edges attached to a vertex (or node). Loops are counted twice.
  • Walk- A sequence of adjacent graph vertices and edges such that each edge and vertex is distinct.

Topics of interest

Topics of interest in graph theory, and some examples of questions posed in graph theory, include:

  • Graph coloring- how many colors are needed to color a graph such that no adjacent vertices are the same color? (See the Four Color Theorem)
  • Spanning trees- how many different spanning trees exist for a given graph? Given a weighted graph, what is the spanning tree of least total weight? (See Kruskal's Algorithm)
  • How can we tell if a graph is cyclic or acyclic? Planar or non-planar?
  • Isomorphism- When do two graphs have essentially the same structure?

And so on.

Examples of Geometry

To see all Graph Theory related pages, head over to the Graph Theory category.


Other Links