tree

tree

an undirected, connected, acyclic graph

depth-first tree search

starts at the root vertex and explores as far as possible along each branch before backtracking (we don't have to know the steps yet)

breadth-first tree search

starts at the root vertex and explores all adjacent vertices at the present depth before moving onto the next depth level

forest

an undirected, acyclic graph- unlike trees they don't have to be connected (essentially a graph of multiple trees and/or disconnected individual vertices)

cayley's formula

for a graph with n vertices, the number of trees that can be created from it is: NT = n^(n-2)

cayley's formula and non-isomorphic trees

cayley's formula counts all trees within isomorphisms, the number of non-isomorphic trees is smaller for low-order graphs the number of NITs can be found by systematically considering the trees with the highest possible maximum degree (n-1 which is a star where one root vertex connects to all other vertices) to the lowest possible maximum degree (2 which is a chain)

trees size and order

E = #V - 1

any connected graph with n vertices and n - 1 edges is a tree the removal of any edge disconnects T, and the addition of any edge creates a cycle any two vertices of T are connected by exactly one path

rooted tree

a hierarchical tree where one vertex is chosen as the "root" all vertices have parent except the root vertex, all vertices have child vertices except the "leaf" vertices at the end

binary tree

a tree where each vertex has at most two children

spanning tree

the spanning tree for a graph is a subgraph that includes every vertex

minimum spanning tree

the spanning tree with the smallest possible sum of edge weights

primm's algorithm

a greedy (fast but doesn't always find the optimal solution) algorithm to find minimum spanning trees -start at any vertex and add that to the MST -add the vertex across the adjacent edge with the lowest weight to the MST -add the vertex across the lowest-weighted edge adjacent to any vertex in the MST, to the MST (only for vertices that aren't already in the MST) -repeat the last step untill all vertice are in the MST

directed acyclic graphs

a connected, directed, acyclic graph with a topological order (every edge is directed from earlier to later in the sequence) a vertex is defined as a source vertex if all adjacent edges are leaving it, and as a sink vertex if all adjacent edges are entering it