Project Links Logo Artwork
Graph Theory: Industrial Drilling
Home > Graph Theory: Industrial Drilling > Foundations > Edges and Vertices
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

Edges and Vertices

Now that you understand what a graph is, let's define some useful terms relative to the edges and vertices of a graph:

If an edge is an edge in a graph, then

  1. is said to be incident with vertices and .
  2. and are also said to be incident with .
  3. and are adjacent to one another.

The degree of a vertex is the number of vertices adjacent to . (This equals the number of edges incident with ).

Example:
Degree

Figure 5: Degree

In this graph, vertices , , and have degree 2, while vertex is an isolated vertex (its degree is 0). Notation: .



An isolated vertex is a vertex of degree . In the example graph above, is an isolated vertex.

A graph is regular if the degrees of all vertices are equal. A graph is r-regular if , .

When are graphs the same?

A graph is fully defined by its vertex and edge sets. However, the same graph can be drawn differently. Different ways to represent the same graph are often considered immaterial. This approach is captured by the definition of isomorphic graphs:

Isomorphism

Two graphs and are called isomorphic if there is a one-to-one correspondence between and which preserves all adjacencies.

 
 
go backgo forward
go backgo forward