scoresvideos
Data Structures
Table of Contents
Unit 10 Overview: Graphs and their Representations
10.1 Graph Terminology and Properties
10.2 Graph Representation Methods
10.3 Graph ADT and Basic Operations

🔁data structures review

10.1 Graph Terminology and Properties

Citation:

Graphs are powerful data structures that model relationships between entities. They consist of vertices (nodes) and edges, which can be directed or undirected, weighted or unweighted. This flexibility allows graphs to represent various real-world scenarios, from social networks to road systems.

Vertices in graphs have properties like degree, which measures their connectivity. Different graph types, such as complete, bipartite, and connected graphs, have unique characteristics that make them suitable for specific applications. Understanding these fundamentals is crucial for solving complex problems using graph algorithms.

Graph Fundamentals

Vertices and edges in graphs

  • Graph is a data structure with vertices (nodes) and edges connecting them
  • Vertices represent entities or objects
  • Edges represent relationships or connections between vertices
    • Can be weighted with numerical value for cost or strength of connection
    • Can be unweighted with no associated value, just represents connection
    • Can be directed with specific direction from one vertex to another (arrow)
    • Can be undirected with no specific direction, bidirectional connection

Directed vs undirected graphs

  • Directed graphs (digraphs) have edges with specific direction (arrows)
    • Social media follower relationships (edge from user A to B indicates A follows B)
    • Web page links (edge from page A to B indicates hyperlink from A to B)
    • Task dependencies (edge from task A to B indicates A must be completed before B)
  • Undirected graphs have edges without specific direction, bidirectional connections
    • Social networks representing friendships (edge between two people indicates mutual friendship)
    • Road networks (edge between two cities represents connecting road)
    • Collaboration networks (edge between two individuals indicates they have worked together on a project)

Vertex Properties

Degree concepts for vertices

  • Degree of vertex in undirected graph is number of edges incident to that vertex (number of edges connected to vertex)
  • In directed graph, vertices have two types of degrees:
    • In-degree: Number of incoming edges to a vertex (edges that point towards vertex)
    • Out-degree: Number of outgoing edges from a vertex (edges that point away from vertex)
  • Total degree of vertex in directed graph is sum of its in-degree and out-degree

Classification of graph types

  • Complete graphs:
    • Every pair of vertices is connected by an edge
    • In complete graph with $n$ vertices, there are $\frac{n(n-1)}{2}$ edges
  • Bipartite graphs:
    • Vertices can be divided into two disjoint sets
    • Every edge connects a vertex from one set to a vertex in the other set
    • No edges between vertices within the same set
    • Job assignment problems (one set represents workers, other set represents tasks)
    • Student-course enrollment (one set represents students, other set represents courses)
  • Connected graphs:
    • There exists a path between every pair of vertices
    • Starting from any vertex, possible to reach any other vertex by traversing edges
    • Graph that is not connected is called disconnected graph, consists of two or more connected components

Key Terms to Review (13)

Graph: A graph is a mathematical structure used to represent relationships between pairs of objects, consisting of vertices (or nodes) connected by edges. In data structures, graphs are essential for modeling various real-world scenarios such as networks, social connections, and pathways. They can be directed or undirected, weighted or unweighted, and provide a versatile way to analyze complex relationships in data.
Connected graph: A connected graph is a type of graph where there is a path between every pair of vertices, ensuring that all vertices are accessible from one another. This property is crucial as it determines the overall structure and usability of the graph, particularly in algorithms related to network connectivity and resource optimization. In practical terms, a connected graph allows for efficient traversal and analysis, which are essential in applications like minimum spanning trees and shortest path computations.
Bipartite graph: A bipartite graph is a special type of graph where the set of vertices can be divided into two distinct groups such that no two vertices within the same group are adjacent. This structure allows for modeling relationships between two different sets of entities, making it particularly useful in scenarios like matching problems or representing networks. Each edge in a bipartite graph connects a vertex from one group to a vertex from the other, and this unique property distinguishes it from other types of graphs.
Degree of a vertex: The degree of a vertex is the number of edges that are incident to it in a graph. It reflects the connectivity of the vertex and is fundamental in understanding various properties of graphs, such as whether a graph is connected or the presence of isolated vertices. The degree can be categorized into in-degree and out-degree in directed graphs, providing deeper insights into the flow and relationships within the graph structure.
Unweighted graph: An unweighted graph is a type of graph where edges do not have any associated weights or costs, meaning all edges are considered equal. This simplifies the analysis and traversal of the graph, making it easier to implement algorithms that rely on relationships rather than numerical values. In an unweighted graph, the focus is primarily on the connectivity and structure of the nodes rather than the distances or costs associated with traversing the edges.
Complete graph: A complete graph is a type of graph in which every pair of distinct vertices is connected by a unique edge. This means that in a complete graph, there are no missing edges, making it fully connected. The number of edges in a complete graph can be calculated using the formula $$E = \frac{n(n-1)}{2}$$, where 'n' is the number of vertices. Complete graphs are important because they represent the most connected structure possible among a set of points.
Out-degree: Out-degree refers to the number of edges that originate from a given vertex in a directed graph. This concept is essential for understanding the structure and behavior of directed graphs, as it helps determine how many connections a particular vertex has leading away from it. Out-degree plays a crucial role in analyzing graph properties such as connectivity, flow, and traversal algorithms.
In-degree: In-degree refers to the number of incoming edges directed toward a particular vertex in a directed graph. It provides insight into the connectivity and structure of the graph by indicating how many other vertices are connected to the specific vertex. This measure is crucial for understanding flow, paths, and relationships within the graph, and it plays a key role in algorithms that analyze directed networks.
Weighted graph: A weighted graph is a type of graph in which each edge is assigned a numerical value, known as a weight, representing the cost, distance, or time associated with traversing that edge. This allows for more complex representations of relationships between vertices, enabling algorithms to compute paths based on these weights and find optimal solutions for various problems.
Edge: An edge is a fundamental component in graph theory, representing a connection or relationship between two vertices (or nodes) in a graph. In the context of various data structures, edges can signify relationships in hierarchical structures like trees, or connections in more complex networks, playing a critical role in understanding and navigating these structures.
Directed graph: A directed graph, or digraph, is a set of vertices connected by edges, where each edge has a direction associated with it. This means that the edges are ordered pairs, indicating a one-way relationship from one vertex to another. Directed graphs are essential in representing structures where relationships are not mutual, such as web pages linking to each other or tasks that depend on others.
Vertex: A vertex is a fundamental part of a graph, representing a distinct point where edges meet. It serves as a key component in various graph representations and plays a crucial role in the properties and operations related to graphs, including traversal algorithms and data structure implementations.
Undirected graph: An undirected graph is a set of objects called vertices connected by edges, where the edges have no direction. This means that if there is an edge connecting vertex A to vertex B, you can traverse from A to B and from B to A freely, highlighting the bidirectional nature of connections. In these graphs, relationships are symmetrical, making them suitable for representing mutual relationships like friendships or road networks.