Networks

• Complete bipartite graph

  Every vertex of one group is connected to every vertex of the other group
• multiple edge

  (more than one edge linking the two same vertices)
• Planar graph


  •Planar graphs are graphs that can be drawn with no edges crossing over
• Edge


  connection between two vertices
• vertex


  point or endpoint
• Euler's rule


  V+F-E=2
• Degree of vertex the number of edges that meet at that vertex, with loops counted twice
• Arc


  an edge that has direction (also called a directed edge)
• Traversability


  the ability to go over/ trace over every edge just once
• Weighted graph


  A graph in which numerical values are assigned to edges
• Simple graph


  a graph with no loops or multiple edges
• Bridge: an edge which if removed, creates a disconnected graph
• Tree


  A network in which every edge is a bridge.

  Features include:

  • the number of edges= number of vertices - 1
  • Always planar
  • Two vertices are connected by 1 edge
  • 1 face
• Complete graph


  A graph in which all vertices are connected by only 1 edge
• Number of edges in Kn


  $n(n-1)/2$

  where n= number of vertices
• Subgraph


  a section of a larger graph with no additional edges or vertices
• Bipartite graph


  A graph which is split into two distinct groups which are connected across the graph. Each vertex of the same group is not connected
• Digraph


  •Digraph (directed graph): a graph containing edges with an indicated direction. Directed edges are commonly known as arcs and are shown with an arrow.
• In degree 


  Featured in digraphs. Is the number of arcs ending at vertex
• Out-degree


  Featured in digraphs. Is the number of arcs starting at a vertex
• Steps for finding shortest path via trial and error


  1.Name vertices

  2.Start going through each path combination, listing the path you travelled and the distance/time
• Finding the shortest path (bubble method)

  1.Circle each vertex

  2.Label edges with total distance from starting vertex

  3.Label the shortest path distance in the centre of your circle

  4.Highlight shortest path
• When asked to draw the complement of a graph...


  you draw a network showing what has not happened
• Walk

  •a sequence of connected vertices such that from each vertex there is an edge to the next vertex. Walks can include repeated edges and vertices.
• Trail


  •A trail is a walk which does not contain repeated edges. Vertices can be repeated
• Path


  •A path is a walk with no repeated edges and vertices
• Closed path (cycle)


  •A path which starts and ends at the same vertex is a closed path and is also called a cycle. You must refer to it as a cycle to get full marks.
• Open: start and ends at different vertices

  Closed: starts and ends at the same vertex
• Eulerian trail


  •trail that includes every edge in a graph but only once
• Closed eulerian trail


  •an eulerian trail starting and ending at the same vertex
• Open/semi-eulerian trail


  •eulerian trail that starts and ends at different vertices
• Eulerian graph


  a connected graph containing a closed eulerian trail
• Semi-eulerian graph


  a connected graph containing an open eulerian trail
• Conditions for eulerian graph

  Each vertex has an even degree (0 odd degrees) and thus a closed eulerian trail exists
• Conditions for a semi-eulerian graph

  Two vertices have an odd degree (open eulerian trail exists). When drawing the trail you must start and finish odd.
• Hamiltonian path


  •a walk that includes every vertex in a graph just once (no repeat vertices or edges)
• Hamiltonian cycle


  •a Hamiltonian path that starts and ends at the same vertex
• Hamiltonian graph


  •a connected graph that contains a Hamiltonian cycle
• Semi- hamiltonian graph


  •a connected graph that contains an open Hamiltonian path
• Face


  the regions of a graph that are bound by edge. includes outside region