Basic Properties of a Graph
A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.
The basic properties of a graph include:
- Vertices (nodes): The points where edges meet in a graph are known as vertices or nodes. A vertex can represent a physical object, concept, or abstract entity.
- Edges: The connections between vertices are known as edges. They can be undirected (bidirectional) or directed (unidirectional).
- Weight: A weight can be assigned to an edge, representing the cost or distance between two vertices. A weighted graph is a graph where the edges have weights.
- Degree: The degree of a vertex is the number of edges that connect to it. In a directed graph, the in-degree of a vertex is the number of edges that point to it, and the out-degree is the number of edges that start from it.
- Path: A path is a sequence of vertices that are connected by edges. A simple path does not contain any repeated vertices or edges.
- Cycle: A cycle is a path that starts and ends at the same vertex. A simple cycle does not contain any repeated vertices or edges.
- Connectedness: A graph is said to be connected if there is a path between any two vertices. A disconnected graph is a graph that is not connected.
- Planarity: A graph is said to be planar if it can be drawn on a plane without any edges crossing each other.
- Bipartiteness: A graph is said to be bipartite if its vertices can be divided into two disjoint sets such that no two vertices in the same set are connected by an edge.
Graph Data Structure Notes for GATE Exam [2024]
Graphs, a fundamental concept in computer science and mathematics, serve as powerful tools for modeling and solving a myriad of real-world problems. As aspirants gear up for the GATE Exam 2024, a comprehensive understanding of graph data structures becomes paramount. These notes aim to provide a concise and illuminating guide to graph data structures, unraveling the principles, representations, and algorithms associated with them, all of which are essential for mastering this topic in the GATE examination.
Table of Content
- What is Graph?
- Components of a Graph
- Breadth First Search or BFS in Graph
- Depth First Search or DFS in Graph
- Types of Graphs
- Representations of Graph
- Basic Properties of a Graph
- Applications of Graph Data Structure
- Advantages of Graph:
- Disadvantages of Graph
- Gate Previous Year Problems on Graph Data Structure
Contact Us