# Introductions to Graphs

## What is a Graph?

- In mathematics and computer science, a graph is a fundamental data structure used to represent relationships between objects.
- A graph consists of a set of nodes (vertices) and a set of connections (edges) that link these nodes.
- Each edge can connect two nodes, and it may or may not have a direction.

**Examples of Graphs**

**Social Networks**: Think of Facebook or Twitter. Users are represented as nodes, and friendships or followership as edges in the graph.**Transportation Networks**: In a city, streets and intersections can be represented as nodes, and roads as edges.**Internet**: Webpages are nodes, and hyperlinks are edges.

## Degree of a Vertex of a Graph

### What is Vertex Degree?

- The degree of a vertex in a graph is the number of edges connected to it. It indicates how many other vertices are directly linked to the given vertex.

**Example**

Consider a simple graph with vertices A, B, C, and D. If A is connected to B, C, and D, its degree is 3.

## Handshaking Theorem

### What is the Handshaking Theorem?

- The Handshaking Theorem states that in any graph, the sum of the degrees of all vertices is equal to twice the number of edges.
- This theorem helps analyze the relationships between vertices and edges in a graph.

**Example**

In a graph with 4 vertices and 6 edges, the sum of the degrees of all vertices must be 12, following the Handshaking Theorem.

## Different Types of Graphs

**Undirected Graph**: Edges have no direction, and connections are symmetric.**Directed Graph (Digraph)**: Edges have a direction, indicating one-way relationships.**Weighted Graph**: Edges have weights or values associated with them.**Cyclic Graph**: Contains at least one cycle (a closed path).**Acyclic Graph**: Contains no cycles.**Connected Graph**: Every pair of vertices is connected by a path.

## What is Subgraph?

- A subgraph is a graph formed by selecting a subset of vertices and edges from a larger graph while preserving their connections and relationships.
- It allows for the examination of smaller, specific parts of a graph.

## Matrix Representation of a Graph

### Adjacency Matrix

- An adjacency matrix is a square matrix used to represent connections in a graph.
- Rows and columns correspond to vertices, and the values indicate whether there is an edge between two vertices.

### Incidence Matrix

- An incidence matrix is used to represent relationships between vertices and edges in a graph. Rows correspond to vertices, and columns correspond to edges.
- It shows which vertices are connected to which edges.

## What are Isomorphic Graphs?

- Two graphs are isomorphic if they have the same structure, meaning the arrangement of nodes and edges is the same, but the labels may differ.
- Isomorphism implies that the graphs are essentially the same, just represented differently.

## Path and Circuit

### Floyd’s Algorithm

- Floyd's algorithm finds the shortest paths between all pairs of vertices in a weighted graph.
- It's helpful for solving problems like navigation and route optimization.

### Warshall Algorithm

- The Warshall algorithm determines the transitive closure of a directed graph.
- It helps identify all pairs of vertices that are reachable from each other.

## What is a Connected Graph?

- A connected graph is a graph where there is a path between any pair of vertices.
- It's a single, unified structure without isolated components.

## Hamiltonian Graph

- A Hamiltonian graph is a graph that contains a Hamiltonian cycle - a cycle that visits each vertex exactly once.

## Euler Graph

- An Euler graph is a graph that contains an Eulerian circuit - a circuit that passes through each edge exactly once.

## Graph Coloring

### Vert

- Vertex coloring assigns colors to vertices in such a way that no two adjacent vertices have the same color.
- It's used in scheduling, map coloring, and more.

### Edge Coloring

- Edge coloring assigns colors to edges in a graph so that no two incident edges have the same color.

### Map Coloring

- Map coloring is a real-world application of graph coloring where regions on a map are colored so that no adjacent regions have the same color, like coloring countries on a map.

## Conclusion

In conclusion, graphs are versatile tools for representing and analyzing relationships in various fields, from social networks to transportation systems. Understanding concepts like vertex degrees, handshaking theorems, matrix representations, and different graph types can help in solving complex problems and making data-driven decisions.