# Graph Theory

Graph theory is the study of mathematical structures used to model relations between objects

- Undirected Graphs
- Directed Graphs
- Incidence (Neighborhoods)
- Self-loops
- Subgraphs
- Paths
- Properties
- Trees
- Hypercubes
- References

## Undirected Graphs

An undirected graph is defined as a tuple containing a set of vertices and a set of edges, where the vertices correspond to the graph nodes, and the edges correspond to the connections between them.

For example: is a graph which three nodes, where A is connected to B and C.

Notice that the edges are declared by unordered sets, therefore we call these
kinds of graph *undirected*.

Undirected graphs donâ€™t have the concept of more than one edge between a set of vertices, therefore the edges must be a set, and not a multi-set.

Given a set of vertices , the set of all possible connections is denoted as . Notce that given edges , is must hold that .

### Degree

The degree of a vertex is the number of edges incident to such vertex. Formally, . A vertex whose degree is 0 is called an isolated vertex.

## Directed Graphs

A directed graph is similar to an undirected graph with the addition of encoding the direction of the edges. A directed graph consists of a set of vertices and a set of edges containing tuples instead of other sets. For example: where and denotes a directed graph where A is connected to B, but B is not connected to A, since .

If each edge goes in both directions, then the graph is undirected.

### Degree

Directed graphs have two types of degrees. The **in-degree** of a vertex is the
number of edges *to* that vertex. The **out-degree** of a vertex is the number
of edges *from* that vertex to other vertices.

The degree if a vertex, denoted , is the cardinality of its neighborhood. Notice that given a graph with vertices and number of edges, then .

## Incidence (Neighborhoods)

If an edge connects vertices A and B, then we say such vertices are
*neighbors*, or *adjacent*. We also say that such edge is *incident* on A and
B. Formally, given edges and vertices , the neighborhood of
is .

## Self-loops

An edge from a node to itself is called a self-loop.

## Subgraphs

A graph is a subset of another graph if its nodes and edges are subsets of the
other graph. Given graphs and , is a *subgraph* of if and .

## Paths

A path is a sequence of neighbor edges in a graph that goes from vertices A to B. Given , a valid path from B to C would be .

A path is *simple* if the starting and ending vertices are different. A
**cycle** is a path which starts and ends in the same vertex.

A path from A to B with repeated edges is called a *walk* from A to B. A *tour*
is a walk that starts and ends on the same vertex.

A walk that that uses each edge exactly once is called an Eulerian walk. If such walk starts and ends on the same vertex, then its called an Eulerian tour.

## Properties

### Connected

A graph is said to be connected if there is a path between any two distinct vertices. Notice that even a disconnected graph consists of a collection of connected components.

### Even Degree

A graph in which all vertices have even degrees.

### Planar

A graph is planar if it can be drawn without overlapping edges.

### Complete

A complete graph contains the maximum number of edges possible. For every pair
of distinct vertices, there exists an edge between then. We say that a complete
graph is *strongly connected*. In the case of directed graphs, for every pair
of vertices and the graph contains two edges: and
.

denotes the unique complete graph on vertices. The number of edges in is . The degree of any vertex in is .

## Trees

A graph is a tree if it contains no cycles. A tree is a connected acyclic
graph. Its a minimally connected graph, the opposite of a complete graph, and
the most effective graph we can use to connect any set of vertices. A tree has
number of edges. A node with a degree of 1 is called a *leave*.

Removing any single edge disconnects the graph and adding any single edge creates a cycle.

### Rooted Trees

A rooted tree is a tree with a designated *root node*. The botton-most nodes
are called *leaves*, and the intermediate nodes are called *internal nodes*.

The depth of a tree is determined by the length of the longest path from the
root to a leaf. A tree may contain many *levels*, which are determined by the
length of every subsets of the longest path that determines the depth.

## Hypercubes

Hypercubes are a case of graphs that can be used to achieve strong connectivity without an exhaustive number of edges. The number of vertices in an hypercube is . The number of edges in an n-dimension hypercube is .

A line is a 1-dimension hypercube, a square of a 2-dimension hypercube, and a cube is a 3-dimension hypercube. Notice that in any hypercube, the vertices have number of neighbors where equals the dimension of the hypercube.

In the case of a 3-dimension hypercube, there are 8 vertices where each has 3 neighbors, so the graph has a total of 12 edges. A complete graph of the same number of vertices would require 28 edges.

## References

- https://en.wikipedia.org/wiki/Graph_theory
- http://www.eecs70.org/static/notes/n5.html