BASIC GRAPH THEORY

Introduction

 

In the real world many problems are represented in terms of objects and connections between them. For example, in Railway route map we might be interested in questions like: “What is the fastest way to go from Lucknow to Delhi?” To answer these questions, we use Graph Data structures.

A graph is simply a way of encoding pairwise relationships among a set of objects. It consists of a collection of V nodes and E edges. Edge simply connects two of the nodes but not necessarily. An edge can also go start and end on same node, these types of edges are called self-loops. We will discuss them on later posts.

Types of Edges

· Directed Edge

• Ordered Pair of Vertices (u, v).
• First Vertex is Origin
• Second Vertex is Destination
• Its like one-way road

· Undirected Edge

• Unordered pair of vertices (u, v).
• Its like two-way road.

Types of Graphs

• Directed Graph

 

• All edges are Directed
• It is like Route Network

• Undirected Graph

• All Edges are Undirected
• Its like Flight network

Important Points You Should Know

•      A degree of vertex is the number of edges incident on it.
•     Two edges are parallel if they connect the same pair of vertices.

•     A graph with no cycles is called a Tree. A Tree is an acyclic connected graph.

•     A self-loop is an edge that connects a vertex to itself.

•     Graphs with relatively few edges are called Sparse Graphs.
•     A graph is connected if there is a path from every vertex to every other vertex.
•     If graph is not connected, then is consists of a set of Connected Components.

•     Graphs with all edges present are called Complete graphs.
• Weighted graphs have weights assigned to each edge or node. 

NEW TOPICS ARE BEING ADDED 💚