Introduction to Graphs

[qingquan-li]

1. Definition of Graph

A graph is a collection of nodes (or vertices) and the connections (or edges) between them.

2. Properties of Graphs

1. Vertices (Nodes): The fundamental units or points, often representing entities.
2. Edges (Links): The connections between vertices, representing relationships or interactions.
3. Directed vs. Undirected: Graphs can have directed edges (where the relationship is one-way) or undirected edges (where the relationship is bidirectional).
4. Weighted vs. Unweighted: Edges in graphs may have weights, representing the cost or strength of the connection.
5. Cyclic vs. Acyclic: Graphs can have cycles (paths that start and end at the same vertex) or be acyclic (no cycles).
6. Connected vs. Disconnected: In a connected graph, there is a path between every pair of vertices. A graph is disconnected if it is not connected.
7. Sparse vs. Dense: A graph is sparse if it has few edges compared to the number of vertices, and dense if it has many edges.

3. Applications of Graphs

• Networking: Representing and managing networks like LANs, the Internet, etc.
• Social Networks: Modeling relationships and interactions between entities.
• City Traffic Routing: Optimizing paths and traffic flows.
• Project Scheduling: Scheduling tasks in project management.
• Biology: Modeling and analyzing biological networks, like neural or genetic networks.

4. Types of Graphs

1. Simple Graph

A graph with no loops and no more than one edge between any two vertices.

A --- B
|     |
|     |
C --- D

2. Multigraph

A graph which may have multiple edges and loops.

A --- B
|\   /|
| \ / |
| / \ |
|/   \|
C --- D
 \___/

3. Weighted Graph

A graph where edges have weights.

A --3-- B
|       |
4       2
|       |
C --1-- D

4. Directed Graph (Digraph)

A graph where edges have directions.

A ---> B
^     /
|    /
|   /
v  v
C <--- D

5. Tree

A connected, acyclic graph.

    A
   / \
  B   C
 /   / \
D   E   F

6. Bipartite Graph

A graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.

U:    V:
A --- 1
|     |
B --- 2
|     |
C --- 3

7. Complete Graph

A graph in which every pair of distinct vertices is connected by a unique edge.

   A
  / \
 /   \
B --- C
 \   /
  \ /
   D

5. Difference Between Graph and Tree

A tree is a type of graph but with specific properties:

• Trees have no cycles (acyclic).
• In a tree, any two vertices are connected by exactly one path.
• Trees have a hierarchical structure, often with a designated root node.

6. Other Concepts

• Subgraph: A graph formed from a subset of the vertices and edges of another graph.
• Degree of a Vertex: Number of edges incident to a vertex (in a directed graph, separate in-degree and out-degree).
• Path and Cycle: A path is a sequence of edges connecting a sequence of distinct vertices. A cycle is a path that starts and ends at the same vertex.
• Adjacency Matrix and List: Ways to represent a graph in computer memory.
• Graph Algorithms: Algorithms like Dijkstra's for shortest paths, Prim's and Kruskal's for minimum spanning trees, and algorithms for searching (DFS, BFS), etc.