 |
 |
  |
|
|
|
Another word for edge.
Two vertices are adjacent if they are connected by an edge. We often call these two vertices neighbors. Two adjacent vertices:
 |
In a complete graph, all pairs of vertices are adjacent. Here is the complete graph on five vertices:
The degree of a vertex is the size of its neighborhood. The degree of a graph is the maximum degree of all of its vertices.
The diameter of a graph is the length of the longest path you are forced to use to get from one vertex to another in that graph. You can find the diameter of a graph by finding the distance between every pair of vertices and taking the maximum of those distances.
The distance between two vertices is the length of the shortest path between them.
An edge connects two vertices in a graph. We call those two vertices the endpoints of the edge. Another word for edge is arc. Here are the edges of a graph (in red):
A graph is basically a collection of dots, with some pairs of dots being connected by lines. The dots are called vertices, and the lines are called edges.
More formally, a graph is two sets. The first set is the set of vertices. The second set is the set of edges. The vertex set is just a collection of the labels for the vertices, a way to tell one vertex from another. The edge set is made up of pairs of vertex labels from the vertex set. On this site, we will be more interested in diagrams of graphs than the sets that make them up.
Here is a diagram of a graph, and the sets that the graph is made from:
 |
V={A,B,C,D} --The vertex set. E={(A,B) , (A,C) , (B,C) , (B,D)} --The edge set. |
| A graph diagram. | The sets that make up a graph. |
Two graphs are isomorphic if they are they same graphs, drawn differently. Two graphs are isomorphic if you can label both graphs with the same labels so that every vertex has exactly the same neighbors in both graphs. Here are two isomporphic graphs:
Labels are just the names we give vertices and edges so we can tell them apart.
The neighborhood of a vertex is all the vertices that it is adjacent to (all of the vertex's neighbors). Here we have a vertex (in blue) and the vertices in its neighborhood (in red):
Another word for vertex.
The order of a graph is the number of vertices it has.
A path in a graph is a sequence of vertices from one vertex to another using the edges. The length of a path is the number of edges used, or the number of vertices used minus one. A path cannot visit the same vertex twice. Here is an example of a path:
More formally, a graph is a sequence of distinct vertices of the form <x0, x1, ..., xn> such that xi and x(i+1) are adjacent for i=0,...,n-1.
A planar graph is a graph that you can draw on a flat surface, or plane, without any of the edges crossing. Graphs that cannot be drawn on the plane without crossed edges are called non-planar graphs. Any graph that has either of the following graphs as subgraphs are non-planar:
In a regular graph, each vertex has the same degree.
The size of a graph is the number of edges it has.
A subgraph of a graph is some smaller portion of that graph. Here is an example of a subgraph:
|
 |
| A graph | A subgraph |
A vertex is a 'dot' in a graph. The plural of vertex is 'vertices', as in, 'this graph has five vertices'. Another word for vertex is node. Here are the vertices of a graph (in red):
Menus: Main / Tutorial / Exercises / Activities/ Home
|
 |
|