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.

• 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.

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.

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