**Graph Basics**

By:
David
On:
Mon 29 May 2017
Pageviews: 18

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