# Graph¶

A graph is consists of nodes and edges

- Path: A path leads from node a to node b through edges of the graph.
- Length: The length of a path is the number of edges in it.
- Cycle: A path is a cycle if the first and last node is the same.
- Simple: A path is simple if each node appears at most once in the path.

## Terminologies¶

### 1. Connectivity¶

A graph is connected if there is a path between any two nodes.

- Components: Connected parts of its grpah.
- Tree: a tree is a connected graph that consists of $n$ nodes and $n-1$ edges.

### 2. Edge directions¶

A graph is directed if the edges can be traversed in one direction only

### 3. Edge weights¶

In a weighted graph, each edge is assigned a weight. often interpreted as edge length

### 4. Neighbors and degrees¶

Two nodes are $neighbors$ or $adjacent$ if there is an edge between them

- Degree: The degrege of a node is number of its neighbors
- Indegree: The indegree of a node is the number of edges that end at the node
- Outdegree: The outdegree of a node is the number of edges that start at the node

- Regular graph: A graph is regular if the degree of every node is a constant d
- Complete graph: A graph is complete if the degree of every node is $n-1$

### Colorings¶

In a coloring of a graph, each node is assigned a color so that no adjacent nodes have the same color

- Bipartite: A graph is bipartite if it is possible to color it using two colors

Note

It turns out that a graph is bipartite exactly when it does not contain a cycle with an odd number of edges

### Simplicity¶

A graph is simple if no edge starts and ends at the same node(loop), and there are no multiple edges between two nodes.

## Graph representation¶

There are several ways to represent graphs in algorithms. The choice of a data structure depends on the size of graph and the way the algorithm processes it

### 1. Adjacency list representation¶

In the adjacency list representation, each node x in the graph is assigned an

adjacency listthat consists of nodes to which there is an edge from x

- we can efficiently find the nodes to which we can move from a given node through an edge

### 2. Adjacency matrix representation¶

An adjacency matrix is two dimensional array that indicates which edges the graph contains.

- we can efficiently check from an adjacency matrix if there is an edge between two nodes.

### 3. Edge list representation¶

An edge list contains all edges of a graph in some order.

- This is convenient way to represent a graph if the algorithm proesses all edges of the graph and it is not needed to find edges that start at a given node.