Trees and Cycles

Question 1

Isomorphism

Answer 1

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

Question 2

Induced sub graph

Answer 2

A graph you get by selecting only some nodes

Question 3

Counting paths of length n

Answer 3

Count graphs of path graphs on n+1 vertices

Question 4

Closed walk

Answer 4

First and last node are the same

Cycle

Question 5

Cycle

Answer 5

Walk where nodes pairwise disjoint except first and last

Question 6

Trees

Edges formula

Leaves properties

Connection properties

Answer 6

Minimally connected acyclic graph

N-1 edges

Min 2 leaves unless 1 node

Any 2 nodes connected by unique path

Question 7

Cut edge

Answer 7

Removing a cut edge produces more connected components.

NEVER part of a cycle

Question 8

Spanning tree

Answer 8

A tree that connects all vertices of a graph

If graph is connected it’s a tree of all vertices

Question 9

Edge pruning algorithm

Answer 9

Removing edges that are not cut until you get a tree

Question 10

Edge growing

Answer 10

Choosing vertices to include which do not form a cycle until reaching a tree

Question 11

Coloring

Answer 11

Partitioning the graph into colors.

Proper colorable when Andy 2 nodes connected by an edge are different colors

Question 12

Chromatic number

Properties

Answer 12

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!

Question 13

Bipartite

Properties

Answer 13

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

Question 14

Triangle inequality

Answer 14

Distance of v1 v2 <= distance v1 v3 + distance v2 v3

Question 15

Clique

Answer 15

A subset of graph where any two nodes are pairwise connected

Size is number nodes connected

Maximal clique if can’t be extended

Question 16

Independent set

Answer 16

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

Question 17

Complement of graph

Formula for edges

Answer 17

Isomorphic with same vertices but different edges.

(N-2)(n-1)/2 = |e| in complement

Question 18

Rooted tree (directed)

Relationship to DAG

Answer 18

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

Question 19

Rooted directed tree properties

Answer 19

Parent/predecessor points to child/successor(s)

Height is distance from root to furthest leaf measured in number of edges

Question 20

Binary tree

Formula for maximum nodes, leaves, edges

Answer 20

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

Question 21

Binary search tree

Answer 21

A binary tree ordered with a left and right child for each parent