GRAPH THEORY

• Let V be a non-empty set, and E be any set of ordered pairs over V. The pair (V, E) is called a graph. We denote a graph by G = (V, E). V is called the vertex set of G and its elements as vertices, while E is called the edge set of G and its elements as edges.
• Vertices are said to be adjacent if there is an edge that joins them. Edges are said to be adjacent if they share a common vertex. The degree of a vertex is the number of edges at that vertex.
• Special Case: For graphs with loops, you have to add 1 to the degree of the vertex with loops.
• Given a graph G = (V, E). A path in G is a sequence of vertices with no

  repeated edges. A circuit in G is a path that starts and ends at the same

  vertex.
• A graph G is said to be connected if there is a path joining any two of its

  vertices. Otherwise, it is said to be disconnected.
• Given a connected graph G. An edge in G is said to be a bridge if G becomes disconnected when it is deleted. An Euler path is a path that travels through every edge of G. An Euler circuit is a circuit that travels through every edge of G.
• Euler’s Theorem 1

  1. If a graph has any vertices of odd degree, then it cannot have an Euler circuit.
  2. If a graph is connected and every vertex has an even degree, then it has at least one Euler circuit.
• Euler’s Theorem 2

  1. If a graph has more than two vertices of odd degree, then it cannot have an Euler path.
  2. If a graph is connected and has just two vertices of odd degree, then it has at least one Euler path. Any such path must start at one of the odd-degree vertices and end at the other one.
• Euler’s Theorem 3

  1. The sum of the degrees of all the vertices of a graph equals twice the number of edges.
  2. The number of vertices of odd degree must be even.
• Fleury’s Algorithm for Finding Eulerian Circuit (Don’t cross the bridge until you have to)
• Given a connected graph G. A Hamilton circuit is a circuit that passes through each vertex exactly once. A Hamilton path is a path that passes through each vertex exactly once.
• A graph Kn with n vertices is said to be a complete graph if every vertex is adjacent to the other (n − 1) vertices.
• A weighted graph is a graph whose edges have assigned numbers. Such numbers are called weights. Common weights are time, distance and cost. Complete graphs that are weighted are simply called complete weighted graphs.
• 1. Given a complete weighted graph, TSP asks for the circuit of minimum total weight in a graph that visits each vertex exactly once and returns to its starting point.
  2. The optimal solution for a TSP is a Hamilton circuit for a complete weighted graph for which the sum of the weights of the edges traversed is the smallest possible number.
• Three methods to determine a solution for a Traveling Salesman Problem

  • Brute Force Method
  • Nearest Neighborhood Method
  • Cheapest Link Algorithm
• The Brute Force Method

  1. Draw a complete weighted graph for the problem.
  2. List all possible Hamilton circuits.
  3. Find the sum of the weights of the edges for each circuit.

  The circuit with the smallest sum is the optimal solution.
• The Nearest Neighbour Method (an approximate solution)

  1. Draw a complete weighted graph for the problem.
  2. Starting at a designated vertex, pick the edge with the smallest weight and move to the second vertex.
  3. At the next vertex, pick the edge with smallest weight that doesn’t go to a vertex already used.
  4. Continue until the circuit is completed.

  The sum of the weights is an approximation to the optimal solution.
• The Cheapest Link Algorithm

  1. Draw a complete weighted graph for the problem.
  2. Pick the edge with the smallest overall weight. In case of a tie, pick at random.
  3. Pick the edge with the next smallest overall weight that doesn’t:

  3.1 enclose a smaller circuit that doesn’t reach every vertex or

  3.2 result in three chosen edges coming from the same vertex.

  4. Repeat Step 2 until the Hamilton circuit is complete.
• A tree is a graph in which any two vertices are connected by exactly one path.
• Some properties of trees:

  1. A tree has no circuits.
  2. Trees are connected graphs.
  3. Every edge in a tree is a bridge.
  4. A tree with n vertices has exactly (n − 1) edges.
• A spanning tree for a connected graph G of n vertices is a connected subgraph that is a tree on n vertices. A spanning tree for a graph is a tree that results from the removal of as many edges as possible from the original graph without making it disconnected.
• A minimum spanning tree for a weighted graph is the spanning tree for

  that graph that has the smallest possible sum of the weights.

  To find the underlying minimum spanning tree in a connected graph, one may apply the so-called Kruskal’s algorithm.
• KRUSKAL’S ALGORITHM

  To construct a minimum spanning tree for a weighted graph:

  1. Choose the edge with the lowest weight (and highlight it in color). If there is more than one, pick one at random.
  2. Choose the unmarked edge with the next lowest weight that does not form a circuit with the edges already highlighted, (and highlight it).
  3. Repeat until all vertices have been connected.
• Graph coloring is a function that assigns either the vertices or edges of a graph by a unique color (or label). Graph coloring is specified as either vertex coloring or edge coloring depending whether the vertices or the edges are labelled.
• A graph is said to be a planar graph if it can be drawn in a plane without the edges crossing.
• Given a graph coloring problem, the smallest number of colors needed to color a graph is called the chromatic number.
• Every possible geographical map can be colored with at most four colors in such a way that no two adjacent regions have the same color.
• Two regions are called adjacent if they share a border segment, not just a point. To determine the chromatic number for a given geographical map, it should be represented as a graph where a vertex represents a region, and vertices are adjacent if the region they represent are adjacent in the map.