Computer Science Mojo

~ David's Notes on coding, software and computer science


Graph Basics

Category: Algorithm     Tag: Algorithm   Discrete Math  
By: David     On: Mon 29 May 2017     

Some basic concept on graphs


  • Graph G
    • G = (V, E) vertices/ nodes and edges
    • n = |V|, m = |E|
  • Simple Graph: unweighted, undirected, no self loops, no multi-edges
  • Simple Cycle: Has a path that starts and ends at the same node
  • When is an undirected graph a tree (any two implies the third):
    • no cycles
    • is connected
    • m = n - 1
  • Find path between two nodes: BFS, DFS ( \(\theta (m + n)\) )
  • Bipartite graph: nodes can be divided into two different sets with no vertices connecting within a set
    • is not bipartite <=> contains a cycle with an odd number of nodes
  • Directed graph connectivity
    • strongly connected: every pair of nodes can reach each other
    • connected: for every pair of nodes, one can reach the other
    • weakly connected: every pair of nodes can reach each other if one ignores edge directions
  • Directed acyclic graph (DAG)
    • is a directed graph with no directed cycles
    • Topological ordering: for all the nodes are ordered that a earlier nodes goes to a later node