mogoz

Graphs

tags
Math , Data Structures , Algorithms , Computation and Computer Theory , Complexity Theory

Intro

Basic terms

  • \(0(V * E)\) means that we will check every vertex, and on every vertex we check every edge
    • \(V\) / Node : Set of vertices
    • \(E\) / Edge : Set of edges, connection btwn nodes
  • Path: Sequence of vertices connected by edges
  • Connectivity
    • Verted:Connected: 2 vertices are connected is there’s a path connecting them
    • Graph:Connected: When every node has a path to another node
    • Connected Component

Common problems

Flavors

  • In the diagram, \(n(n-1)\), \(n(n-1)/2\) is the max number of edges.

Cycle

Cyclic

  • Path that starts and ends in the same vertex. All Cycles are Path, but not opposite.
  • A graph can have multiple cycles
  • When you start at Node(x), follow the links, and end back at Node(x)
  • Needs 3 nodes
  • Odd/Even cycles
    • odd : odd no of vertices in the cycle
    • even : even no of vertices in the cycle

Acyclic

A graph that contains no cycles

DAG

Directed, acyclic graph.

Partite

k-partite

  • A graph whose vertices are (or can be) partitioned into k different independent sets.
  • Recognition of \(k>2\) is NP-complete

2-partite (bipartite)

  • aka 2-colorable
  • If there exists and partition of the vertex set into two disjoint-sets
    • i.e \(V_1\) has no adjacent vertices & \(V_2\) has no adjacent vertices
    • If they’re adjacent then one of them is in \(V_1\) and other one is in \(V_2\)
  • Bipartite graphs may be recognized in polynomial time
  • Bipartite graphs cannot have any odd cycles. i.e odd cycles not allowed.
    • Eg. triangle has 3 vertices, and is a cycle. So triangle is not bipartite.
  • How to Tell if Graph is Bipartite (by hand) external link

  • Types

    • Complete: Every vertex in one set is connected to every vertex in the other set.
    • Matching: Each vertex is connected to at most one other vertex from the opposite set.
    • Planar: Can be embedded in the plane without any edges crossing.

Others

  • Regular: Every vertex has the same degree.
  • Multigraph: Allows multiple edges between the same pair of vertices.
    • Eg. Being able to swim across a river or take a raft across the same river is an example in games.

Graph representation

Adjacency Matrix

  • \(G=(V,E)\) with \(n\) vertices and \(m\) edges
    • \(M\) is a matrix with \(n \texttimes n\)
    • \(M[i,j] = 1\) if \((i,j) \in E\)
    • \(M[i,j] = 0\) if \((i,j) \notin E\)
  • Space complexity is \((O(n^2)\)
    • Has entry for no-edges
    • Has double entry for undirected edges

Adjacency List

  • Nx1 array of pointers
  • Each element(vertex(\(i\))) points to a linked list of edges incident on vertex \(i\)
  • The direction/order of items in the “edge list” for each “vertex” do not tell anything about if there any network exists between a edge items themselves.
    • i.e A: [B, C], this means A is connected to B and C but tells us nothing about the relation of B and C. This can be confusing because B and C are next to each other in a link list. In other words, link list is just the implementation and not the logical view.
  • List contains list of “what am i adjacent to”
  • Each vertex (N) has set of edges (M). No of edges per vertex is called the degree
    • So, in a way no. of neighbors of some vertex is the degree
  • Space complexity
    • Sparse
      • Space Complexity
        • \(\theta(N+2M) = \theta(n)\) (undirected) or \(\theta(N+M) = \theta(n)\) (directed)
        • total N vertices (items in array)
        • total M edges
        • In undirected, each connected N has the edge mentioned both ways. So 2M
    • Dense
      • Space Complexity: \(\theta(N*N) = \theta(n^2)\)

Graph Nodes

  • Graph Nodes etc. like we do with linked list
  • But we don’t do it this way in practice generally

Viz

Links to this note