Directed Graphs Flashcards
Digraph
Formula max edges
Direct graphs where vertices are ordered.
Self loops are allowed
Anti parallel edges allowed but not double in same direction
Symmetrical connections
Maximum edges is n^2
Degrees in digraph
In or out
Total degree is sum of these
Sum of out degrees = sum in degrees = sum of all nodes in graph
Directed walks and paths
Properties
A sequence of nodes pointing at the next in the sequence
N -> n-> n
A directed path has no repeat vertices
Every vertice has a directed path of length 0 which does not count as a self loop
Directed cycles and isomorphism
Edges always point in same direction
Length is k+1 where k is nodes
A pair of nodes with anti parallel edges is a cycle of length 2 and self loops are length one
Cycle graph isomorphism is mapping of vertices to edges in a permutation
Digraph isomorphism vs undirected isomorphism
No differences
Reachability
A node is reachable when there is a path to it.
Reflexive and transitive - x-y-z then x-z etc, node connected to itself
Strong connectivity
When vertices are reachable form each other.
X y
Reflexive per above
Symmetrically connect each other
Transitive - if there is a chain of strongly connected nodes the ends are strongly connected.
L
Strongly connected components
Properties
Difference SSC, reachability
SCC if any 2 nodes are strongly connected in a maximally connected set (cannot add more)
Any 2 SCCs are disjoint
SCCs partition vertices but not edges!
Look at arrow directions to determine if there is an SCC or just reachability; each vertex must have a path to each other vertex
Sink
A node with only incoming edges and out degree 0. A sink is an SCC of 1
Source
A node with only outgoing edges and in degree 0
It is an SCC to itself
Reduced graph
Cyclic property
Collapse all nodes in each distinct SCC into a single point and show which directed connections it has with other SCCs in the graph
Cannot have directed cycles; if there was a cycle, 2 SCCs would have to be merged
DAG
Properties
Directed acyclic graph
Every one has at least one topo sort
Every dag has at least one source and one sink
Fluid when no node is isolated and there is a directed path from every source to every sink
Topological sort
Properties
A sequence in which every node is part of a permutation appearing only once such that for any edge x->y x appears before y in the sequence (but not always directly before)
Only possible for a dag
First node is a source, last is a sink
Edgeless dag has n! Sorts
Growing and pruning algorithms apply
