# 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

### Stuff

• 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