Graphs and Networks

Degree of a vertex

The number of edges connected to the vertex.

Degree of a vertex format

deg(B)=…

Traversable

A graph is traversable if it can be drawn without taking the pen off the paper and without going over the same edge twice. This occurs when it has exactly zero or two vertices of odd degree.

Loops

A loop is attached twice to a vertex, so it will count as two degrees.

Multiple Edges

Multiple edges are two or more edges that connect the same vertices.

Directed edges

Directed edges are edges which have a direction. They are indicated by the presence of an arrow, and generally indicate 'one way traffic'.

Bridge

A bridge is an edge that if it were to be removed, the graph would no longer be a connected one.

Weighted Graph

Each edge is labelled with some quantity. This quantity might represent the bandwidth, flowrate, distance, capacity etc.

Simple graph/network

An undirected and unweighted (no values) graph with no loops and no multiple edges.

Diagraphs

Any graph that contains at least one directed edge/arc.

Connected graphs

In a connected graph every vertex is connected to every other vertex either directly or via another vertex. That is every vertex can be reached from every other vertex in the graph.

Disconnected graph

A graph is connected if there is a path to all vertices. A graph becomes disconnected if there is a vertex that is not connected to another vertex by an edge.

Complete graph

A complete graph is a simple graph in which every vertex is joined to every other vertex by an edge. A complete graph with 'n' vertices is denoted by Kn

Formula for number of edges in a complete graph

Kn = n(n-1)/2

Walk

A walk is a sequence of vertices that are connected by edges. Any edge or vertex can be repeated.

Trail

A trail is a walk with no repeated edges.

Path

A path is a walk with no repeated edges and no repeated vertices.

Open WTP

starts and finishes at different vertices

Closed WTP

starts and finishes at the same vertices.

Length WTP

The length of a WTP is the number of edges that the sequence includes.

Subgraphs

A subgraph is a part of a larger graph. All of the edges and vertices in the subgraph must exist in the original graph.

Bipartite Graph

Bipartite graph is one where the vertices can be split into 2 distinct 'groups' such that edges only connect to vertices in opposite groups.

Complete bipartite graph

A complete bipartite graph that has every vertex in one group connected to every other group.

Trees

A graph is classified as a tree, if it is simple, connected and contains no possible cycles (closed paths).

Planar graphs

Is undirected, connected, and can be drawn on a plane.

Drawn on a plane meaning

that the graph can be represented without any of its edges crossing (this means it might need to be redrawn)

Euler’s rule

v+f-e=2

Eulerian

A graph that is traversable is known as an Eulerian graph. All about the edges.

This means you can travel along every edge once without doubling over an edge, but the starting and finish points are important.

Points that make a graph Eulerian

• Be connected

• Have all vertices of an even degree

• Starts and finishes at the same vertex

• Vertices may be repeated

• Sometimes the word 'Eulerian Circuit' or 'Eulerian Trail' will be used

Semi-Eulerian

Open Eulerian graph:

• Be connected

• Have exactly two vertices of odd degree

• Will start at one of the odd vertices and finish at the other odd vertex.

Hamiltonian path

A Hamiltonian path involves all the vertices but not necessarily all the edges.

Hamiltonian cycle

A Hamiltonian cycle is a Hamiltonian path that starts and ends at the same vertex.

Hamiltonian graph

• Contain a Hamiltonian cycle

• Vertices nor edges may be repeated (only exception is the start and finishing vertex)

• Any complete graph is Hamiltonian

• A graph may be both Hamiltonian and Eulerian

Semi-Hamiltonian Graph

Contains a Hamiltonian path

Adjacency matrix and degrees

When constructing an adjacency matrix, the degree of a vertex is the number of edges linked to that vertex (with loops counted once). This is contradictory to when we are doing traversability and when we count the edge of the loop twice to determine the degree of the vertex.

Constructing adjacency matrix

A graph containing n vertices can be represented using n x n matrix.

To represent the graph, the names of the vertices are above the columns and to the left of the rows.

Directed graph

Not symmetrical

Undirected graph

Symmetrical

Notes to remember about adjacency matrix

• A '0' represents no edges connecting the vertices.

• A '1' represents 1 edge connecting vertices.

• A number greater than 1 is used when there are multiple edges connecting the same vertices.

• A '1' at the intersection for the SAME vertex indicates a loop.