Graph Theory

Graph

It is a diagram that consists of a set of points (vertices) and a set of lines (edges).

Degree of a Vertex

It is the number of edges which start or finish at the vertex.

Degree of a Graph

It is the sum of the degree of the vertices.

Loop

An edge which starts and finishes at the same vertex.

Multiple Edge

Two edges joining the same two vertices.

Simple Graph

A graph with no loops or multiple edges.

Degenerate Graph

A graph that has no edges.

Connected Graph

A graph in which all vertices are connected via a sequence of edges.

Complete Graph

A graph in which every pair of vertices is connected by an edge.

Subgraph

A part of the original graph. There are no extra vertices or edges that do not appear in the original graph.

Walk

It is a sequence of adjacent edges of a graph.

Trail

It is a walk with no repeated edges.

Path

It is a walk with no repeated vertices and no repeated edges.

Cycle

It is a walk with no repeated edges. The only repeated vertex is the starting (and ending) vertex.

Eulerian Trail

A trail that contains every edge of a graph.

Tree

A connected graph with no cycles, multiple edges or loops..

Spanning Tree

A sub-graph of a connected graph that is a tree and includes all the vertices of the original graph.

Dijkstra's Algorithm

An algorithm for finding the shortest paths between vertices in a weighted graph.

Isolated Vertex

A vertex with degree 0

Bridge

A single edge in a connected graph that, if it were removed would leave the graph disconnected.

Planar Graph

A graph that can be drawn without any edges crossing, except at the vertices.

Circuit

A trail with no repeated edges, that starts and ends at the same vertex.

Hamiltonian Path

A path that visits each vertex exactly once

Hamiltonian Cycle

A walk that visits each vertex exactly once, except for the starting vertex, which is also the ending vertex.

Bipartite graph

Consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.

Critical path

The sequence of activities that determine the earliest time by which the project can be completed

Float or slack time

The largest amount of time an activity can be delayed without affecting the the completion time for the project.

Dummy activity

Is required when activities share some but not all of their immediate predecessors.