# 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

- Contain at least one
**edge.**
- No edge is used twice
- 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

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

# Prim’s Algorithm

*(Minimal Spanning Tree)*

- Start at a vertex
- Find all the edges connected to it
- Choose the cheapest edge
- Now choose the cheapest edge to a vertex we haven’t been to yet.
- 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 } ]

###