# Field:Graph Theory

(Difference between revisions)
 Revision as of 14:15, 15 May 2012 (edit)← Previous diff Current revision (15:48, 23 May 2012) (edit) (undo) Line 1: Line 1: {{Field Page {{Field Page |Field=Graph Theory |Field=Graph Theory - |HeaderImage=Graphexample.JPG + |BasicDesc=Graph theory is the study of '''graphs'''. A graph is informally a collection of points, known as vertices, connected by lines, known as edges. - |HeaderDesc=Example of a planar graph + - |BasicDesc= 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=== ===Basic Terminology===

# 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.

## Contents

[[Image:|300px|thumb|right|]]

### 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.