Graph Basics
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