Trees and Cycles Flashcards
Isomorphism
When there is a 1:1 bijection between graphs
Any 2 complete or grid graphs with same number of nodes are isomorphic
Edges and vertices can be laid out differently but degrees must be same
Induced sub graph
A graph you get by selecting only some nodes
Counting paths of length n
Count graphs of path graphs on n+1 vertices
Closed walk
First and last node are the same
Cycle
Cycle
Walk where nodes pairwise disjoint except first and last
Trees
Edges formula
Leaves properties
Connection properties
Minimally connected acyclic graph
N-1 edges
Min 2 leaves unless 1 node
Any 2 nodes connected by unique path
Cut edge
Removing a cut edge produces more connected components.
NEVER part of a cycle
Spanning tree
A tree that connects all vertices of a graph
If graph is connected it’s a tree of all vertices
Edge pruning algorithm
Removing edges that are not cut until you get a tree
Edge growing
Choosing vertices to include which do not form a cycle until reaching a tree
Coloring
Partitioning the graph into colors.
Proper colorable when Andy 2 nodes connected by an edge are different colors
Chromatic number
Properties
The smallest number of colors that create a proper coloring
Path graph 2
Cycle 2 if even and 3 if odd nodes
Use PHP to find colors!
Bipartite
Properties
A 2 colorable graph.
No cycle of odd length
Any graph has only 2 sub graphs which are bipartite (2x each CC, 2^n if more CCs):
Ex-if you have nodes x, y, z, you can color them r,b,r or b,r,b so that’s two bipartite graphs
Trees bipartite
Triangle inequality
Distance of v1 v2 <= distance v1 v3 + distance v2 v3
Clique
A subset of graph where any two nodes are pairwise connected
Size is number nodes connected
Maximal clique if can’t be extended
Independent set
Opposite of clique. Any two nodes not connected. Graphs are k colorable when there are k independent sets.
Leaves of a tree are an independent set
Complement of graph
Formula for edges
Isomorphic with same vertices but different edges.
(N-2)(n-1)/2 = |e| in complement
Rooted tree (directed)
Relationship to DAG
A pair of a single root node and a whole associated tree.
Any edge in the rooted tree matches any path from the root in the same direction radiating from the root
A DAG from a rooted tree has a root as source and leaves as sink
Rooted directed tree properties
Parent/predecessor points to child/successor(s)
Height is distance from root to furthest leaf measured in number of edges
Binary tree
Formula for maximum nodes, leaves, edges
Rooted tree where every node has AT MOST 2 children
A single node counts; in this case it is root and leaf
When it is completely full it has maximum number of nodes: 2^h+1 - 1 where h is height, and it has 2^h leaves, and 2^h+1 -2 edges
Binary search tree
A binary tree ordered with a left and right child for each parent
