# 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 } ]