Theory of Graphs

Study Notes

Graph Theory

Definition

A graph is a non-linear data structure consisting of nodes (vertices) connected by edges.
Graphs can be directed (digraphs) or undirected.

Types of Graphs

Simple Graph: No multiple edges between any two vertices.
Weighted Graph: Edges have weights or labels.
Multigraph: Multiple edges between any two vertices.
Directed Graph (Digraph): Edges have direction.
Undirected Graph: Edges do not have direction.

Graph Representations

Adjacency Matrix: A matrix where the entry at row i and column j represents the weight of the edge between vertices i and j.
Adjacency List: A list of edges, where each edge is represented as a pair of vertices.
Incidence List: A list of edges and vertices, where each edge is represented as a pair of vertices and each vertex is represented as a list of incident edges.

Graph Terminology

Neighbour: A vertex adjacent to a given vertex.
Degree: The number of edges incident to a vertex.
Path: A sequence of vertices connected by edges.
Cycle: A path that starts and ends at the same vertex.
Connected Graph: A graph where every vertex is reachable from every other vertex.
Subgraph: A graph formed by a subset of vertices and edges from a larger graph.

Graph Applications

Network Modeling: Modeling real-world networks, such as social networks, transportation networks, and computer networks.
Scheduling: Scheduling tasks and resources.
Cryptography: Encryption and decryption algorithms.
Data Analysis: Clustering, classification, and visualization of data.

Graph Algorithms

Breadth-First Search (BFS): Traversing a graph level by level, starting from a given vertex.
Depth-First Search (DFS): Traversing a graph by exploring as far as possible along each branch before backtracking.
Dijkstra's Algorithm: Finding the shortest path between two vertices in a weighted graph.
Topological Sorting: Ordering vertices in a directed acyclic graph (DAG) such that for every edge (u, v), vertex u comes before vertex v.

Lý Thuyết Đồ Thị

Định Nghĩa

Đồ thị là một cấu trúc dữ liệu không tuyến tính gồm các đỉnh (điểm) được nối bởi các cạnh.
Đồ thị có thể là có hướng (đồ thị có hướng) hoặc vô hướng.

Phân Loại Đồ Thị

Đồ Thị Đơn Giản: Không có nhiều cạnh giữa hai đỉnh nào.
Đồ Thị Có Trọng Lượng: Các cạnh có trọng lượng hoặc nhãn.
Đồ Thị Đa Cạnh: Nhiều cạnh giữa hai đỉnh nào.
Đồ Thị Có Hướng: Các cạnh có hướng.
Đồ Thị Vô Hướng: Các cạnh không có hướng.

Đại Diện Đồ Thị

Ma Trận Kề: Một ma trận trong đó ô tại hàng i và cột j biểu thị trọng lượng của cạnh giữa đỉnh i và j.
Danh Sách Kề: danh sách các cạnh, trong đó mỗi cạnh được biểu thị là một cặp đỉnh.
Danh Sách Tương Quan: Danh sách các cạnh và đỉnh, trong đó mỗi cạnh được biểu thị là một cặp đỉnh và mỗi đỉnh được biểu thị là một danh sách các cạnh tương quan.

Thuật Ngữ Đồ Thị

Hàng Xóm: Đỉnh liền kề với đỉnh cho trước.
Bậc: Số cạnh nhất định với đỉnh.
Đường Đi: Một chuỗi các đỉnh được nối với nhau bằng các cạnh.
Vòng: Một đường đi bắt đầu và kết thúc tại cùng một đỉnh.
Đồ Thị Liên Kết: Đồ thị trong đó mỗi đỉnh đều có thể đến được từ mọi đỉnh khác.
Đồ Thị Con: Đồ thị được hình thành từ một tập con của các đỉnh và cạnh của đồ thị lớn hơn.

Ứng Dụng Đồ Thị

Mô Hình Hóa Mạng: Mô hình hóa các mạng thực tế, chẳng hạn như mạng xã hội, mạng vận tải và mạng máy tính.
Lịch Trình: Lập lịch cho các nhiệm vụ và tài nguyên.
Mã Hóa: Mã hóa và giải mã các thuật toán.
Phân Tích Dữ Liệu: Phân tích và trực quan hóa dữ liệu.

Thuật Toán Đồ Thị

Truy Xuất Theo Chiều Rộng (BFS): Truy xuất đồ thị từng lớp một, bắt đầu từ một đỉnh cho trước.
Truy Xuất Theo Chiều Sâu (DFS): Truy xuất đồ thị bằng cách khám phá càng xa càng tốt dọc theo mỗi nhánh trước khi quay lại.
Thuật Toán Dijkstra: Tìm kiếm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng lượng.
Sắp Xếp Thứ Tự: Sắp xếp các đỉnh trong đồ thị có hướng không chứa chu trình (DAG) sao cho với mỗi cạnh (u, v), đỉnh u luôn đi trước đỉnh v.

Description

Khám phá thế giới của đồ thị: định nghĩa, loại đồ thị, các khái niệm cơ bản. Xem xét các loại đồ thị như đồ thị đơn giản, đồ thị có trọng số, đa đồ thị và đồ thị có hướng.