MMW MIDTERMS

• Graph Theory


  Also known as "Mathematics of Graphs", used as a tool to solve some practical problems in our daily living
• Applications of Graph Theory

  • Social networks
  • Communication lines
  • Transportation
  • Modelling traffic
  • Scheduling
  • Route planning
  • Coloring maps
  • Other situations that involve connections
• Graph


  A pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges. Generally, a graph G is represented as G = (V, E), where V is a set of vertices, and E is a set of edges.

  
• Graph

  • Graph with 5 vertices and 7 edges, labelled as graph G, where V = {A, B, C, D, E}, and E = {(A, B), (A, C), (A, D), (B, D), (C, D), (B, E), (E, D)}
  • Graph showing a computer network of a school, where vertices represent computers and edges indicate direct connections

  
• In constructing graphs, the edges can be drawn either straight or curved, the lengths of edges and the placement of the vertices are not important, the graph simply illustrates connections between vertices, and it consists of only one piece

  
• Connected Graph


  A graph is connected if there is a path connecting every pair of vertices

  
• Multigraph


  A graph with multiple edges between the same vertices, these edges are called parallel/ multiple edges

  
• Disconnected Graph


  A graph consisting of two different sections
• Loop


  An edge that connects a vertex to itself
• Simple Graph


  A graph that has no loops or multiple edges
• Null Graph


  A graph with vertices, but no edges, also an example of a disconnected graph
• Isolated Vertex


  A vertex that has no edges incident with it
• Pendant Vertex


  A vertex that has one edge incident with it
• Complete Graph


  A connected graph in which every possible edge is drawn between vertices (without any multiple edges)

  
• Degree of a Vertex


  The number of edges that meet at a vertex, denoted as deg(v), where a loop at a vertex contributes two to the degree of that vertex
• Equivalent Graphs


  Graphs are called equivalent if the edges form the same connections of vertices in each graph
• Euler Circuit


  A circuit that uses every edge but never uses the same edge twice (the path may cross through vertices more than once). A graph will contain an Euler circuit if all vertices have even degree, if a graph has any odd vertices, then it does not have an Euler circuit.
• A graph has an Euler circuit if and only if all vertices have even degree
• Euler Path


  A connected graph contains an Euler path if and only if the graph has two vertices of odd degree with all other vertices of even degree. Every Euler path must start at one of the vertices of odd degree and end at the other. If a graph has more than two odd vertices, then it cannot have an Euler path.
• Euler Path


  • DABCFBEIHGDEH
  • DCBAC
  • CDEFCBAF
• Hamiltonian Circuit


  A path that uses each vertex of a graph exactly once and returns to the starting vertex. A graph that contains a Hamiltonian circuit is called Hamiltonian.
• Hamiltonian Circuit


  • ABCDEA
  • BGFEDACB
  • CADEFGBC
• Hamiltonian Path


  A path that contains every vertex of the graph but does not return to the starting point.

  
• Hamiltonian Path


  • ABGFEDC
  • ECDAB
  • ECABD
• Weighted Graph


  A graph in which each edge is associated with a value called a weight. For each Hamiltonian circuit, the sum of the weights along the edges traversed gives the total distance traveled along that route.
• Greedy Algorithm


  An algorithm to find Hamiltonian circuits in weighted complete graphs, where at each step the cheapest available edge is selected.
• Greedy Algorithm


  • Hamiltonian Circuit: ADBFECA, 117 miles
• Edge-Picking Algorithm


  An algorithm to find Hamiltonian circuits in weighted complete graphs, where edges are selected in order of increasing weight as long as they do not complete a circuit or add a third marked edge to a vertex.
• Edge-Picking Algorithm


  • Hamiltonian Circuit: ADBFCEA, 102 miles
• There is no known shortcut for finding the optimal Hamiltonian circuit in a weighted graph, but the greedy and edge-picking algorithms can provide good solutions for complete graphs
• Planar Graph


  A graph that can be drawn on a plane so that no edges intersect each other (except at vertices). A graph which is not planar is called nonplanar graph.
• Euler's Formula


  In a connected planar graph drawn with no intersecting edges, the relationship v - e + f = 2 is always true, where v is the number of vertices, e is the number of edges, and f is the number of faces.

  
• Graph Coloring


  The process of assigning colors to the vertices of a graph such that no two adjacent vertices are assigned the same color. It ensures that there exists no edge in the graph whose end vertices are colored with the same color.

  
• Chromatic Number


  The minimum number of colors required to properly color any graph such that no two adjacent vertices are assigned the same color.