# Graphs

### Simple Graphs

Are ordered pairs (V, E) where

• V ∈ A set of all Vertices
• E ∈ A set of all Edges

### Multigraph

Are ordered pairs (V, E) where

• V ∈ A set of all Vertices
• E ∈ A bag of all Edges

[A bag is like a set but elements can be repeated]

### Directed Graph

Arrows show direction on a directed graph.

Directed graphs are ordered pairs where

• V ∈ A set of all Vertices
• E ∈ A set of all Edges, where each Edge is an ordered pair of vertices.

### Complete Graph

Every vertex is connected to every other vertex.

### Connected Graphs

A graph is connected if every pair of vertices v,w can be connected by a path which starts at v and ends at w

A path in a graph is a sequence of oriented edges such that the end point of one oriented edge is the beginning of the next.

# Circuits

A circuit is a path that starts and ends at the same point.

### Euler Circuits

• A Euler Circuit visits every edge exactly once.
• All vertices have even degree.

### Hamiltonian Circuits

• A Hamiltonian Circuit visits every **vertex **exactly once.

### Cycles

1. Contain at least one edge.
2. No edge is used twice
3. No vertex (except the starting point) is visited twice.

# Trees

A tree is a connected, undirected simple graph with no cycles.

### Rooted Trees

Select one vertex and orient all edges to form a directed path from the root to all other vertices.

### Leaf

A vertex with no children.

### Internal Vertex

A vertex with children.

### Ancestor

Vertices between the current vertex and the root.

### Descendant

Vertices between the current vertex and the end of the tree.

### Properties Of A Tree

1. Between any pair of vertices, there is only one simple path.
2. Adding a new edge to the tree creates a cycle.
3. Removing an edges causes a disconnected graph.
4. There is at least one leaf.
5. If a tree has two or more vertices, there is at least one vertex with a degree equal to 1
6. Any tree with n vertices has (n – 1) edges.

# Prim’s Algorithm

## (Minimal Spanning Tree)

1. Start at a vertex
2. Find all the edges connected to it
3. Choose the cheapest edge
4. Now choose the cheapest edge to a vertex we haven’t been to yet.
5. Repeat until every vertex has been chosen.

# Probability/Choosing

[  ^{n}P_{r} = frac{n!}{(n-r)!} hspace{10 mm} ^{n}C_{r} = frac{n!}{r!(n-r)!} ]

### O( g(x) ) Definition (Big-Oh)

There exists two constants and such that for , .

### Summation

[ sum_{i=1}^{n} i = 1 + 2 + 3 + … + n = { n(n+1) over 2 } ]

###