Chapter 1: Welcome to the World of Graphs | 欢迎来到图的世界

第 1 章：欢迎来到图的世界

Chapter 1: Welcome to the World of Graphs

---

1.1 你身边的世界充满“关系”

1.1 The World Around You is Full of "Connections"

你有没有想过，我们每天生活的世界，其实是由无数看不见的“关系”编织而成的？当你早晨睁开眼睛，手机里跳出的消息提醒你朋友昨天分享的一张有趣照片；当你走出家门，路边的地铁线路图指引你如何从家到达学校；在学校走廊里，你一眼就能认出哪位同学是你的好朋友，因为你们会互相招手微笑。这些看似平常的场景，其实都隐藏着一个共同的核心概念——关系（Relationship）。

Have you ever wondered that the world we live in every day is actually woven together by countless invisible "relationships"? When you open your eyes in the morning, messages pop up on your phone reminding you of an interesting photo your friend shared yesterday. When you step out of your home, the subway map on the street corner guides you on how to get from home to school. In the school hallway, you can instantly spot which classmate is your good friend, because you wave and smile at each other. These seemingly ordinary scenes actually share a common core concept — relationships.

在这个章节中，我们将一起踏上探索之旅，去发现一种能够表达和理解这些关系的强大工具——图（Graph）。图不仅仅是数学课本里的几何图形，它更是一种描述世界万物之间联系的神奇语言。通过学习图，你将获得一双全新的“透视眼”，能够看到隐藏在日常生活背后的那张巨大而精密的关系网络。

In this chapter, we will embark on an exploration journey together to discover a powerful tool for expressing and understanding these relationships — the Graph. A graph is not just a geometric shape from a math textbook; it is a magical language for describing the connections between all things in the world. By learning about graphs, you will gain a brand new pair of "X-ray glasses" that allows you to see the huge and intricate web of relationships hidden behind our daily lives.

让我们先从几个你一定非常熟悉的场景开始，看看图是如何在这些场景中大显身手的。

Let us start with a few scenes that you must be very familiar with, and see how graphs shine in these scenarios.

---

1.2 社交网络：你的朋友圈就是一张图

1.2 Social Networks: Your Circle of Friends is a Graph

想象一下你打开手机上的社交软件，看到好友列表中有十几个、几十个甚至上百个名字。这些名字之间可不是杂乱无章地排列着的！仔细观察，你会发现一些有趣的现象：小明和小红经常互相点赞，他们是好朋友；小刚虽然不认识小红，但他们有一个共同的好朋友——小明，所以小刚和小红其实是“隔着一个人”的关系；张老师是你们班的班主任，她认识班上的每一个同学，但同学们之间未必都互相认识。

Imagine opening a social app on your phone and seeing dozens or even hundreds of names in your friends list. These names are not randomly arranged! If you look carefully, you will discover some interesting patterns: Xiaoming and Xiaohong often like each other's posts — they are good friends; Xiaogang doesn't know Xiaohong directly, but they share a common friend — Xiaoming, so Xiaogang and Xiaohong are actually "one person apart"; Teacher Zhang is your class teacher, she knows every student in the class, but students may not all know each other.

如果我们把社交网络画成一张图（Graph），那会是什么样子呢？

What would it look like if we drew a social network as a graph?

```mermaid graph LR subgraph 社交网络 Social Network A["小明 Xiaoming 🍎"] --> B["小红 Xiaohong 🍎"] A --> C["小刚 Xiaogang 🍎"] B --> C A --> D["小芳 Xiaofang 🍎"] C --> D E["张老师 Teacher Zhang 👨‍🏫"] --> A E --> B E --> C E --> D end ```

在这张图中，节点（Vertex/Node） 是什么呢？就是每一个“人”。你可以看到图中有小明、小红、小刚、小芳，还有张老师。每一个圆圆圈就像是一个小磁铁，代表着现实世界中的一个实体。

In this graph, what are the vertices (nodes)? They are every "person." You can see Xiaoming, Xiaohong, Xiaogang, Xiaofang, and Teacher Zhang in the diagram. Each circle is like a small magnet, representing an entity in the real world.

而边（Edge） 是什么呢？就是连接两个人之间的关系！小明和小红之间有一条线，说明他们是朋友；小明和小刚之间也有一条线，说明他们也是朋友。但是小红和小刚之间的那条线是什么意思呢？那表示他们虽然不是直接的好朋友，但通过小明的介绍，他们其实也认识！

And what are the edges? They are the relationships connecting people! There is a line between Xiaoming and Xiaohong, indicating they are friends; there is also a line between Xiaoming and Xiaogang, showing they are friends too. But what does the line between Xiaohong and Xiaogang mean? It means that although they are not direct friends, through Xiaoming's introduction, they actually know each other!

这就是图的神奇之处！通过节点和边，我们可以把复杂的社交关系变得清晰可见。原本杂乱无章的好友列表，变成了一张井井有条的“关系地图”。

This is the magic of graphs! Through vertices and edges, we can make complex social relationships clear and visible. The randomly arranged friend list transforms into a well-organized "relationship map."

---

1.3 城市交通：地铁线路图也是图

1.3 City Transportation: Subway Maps are Also Graphs

现在让我们把目光转向城市的公共交通系统。你有没有仔细观察过地铁线路图？那张看起来色彩斑斓的图，其实也是一个完美的“图”的例子！

Now let's shift our attention to the city's public transportation system. Have you ever looked closely at a subway map? That colorful-looking diagram is actually a perfect example of a "graph"!

在地铁线路图上，每一个站点就是一个节点（Vertex）。比如北京地铁一号线上的“天安门东站”“王府井站”“东单站”，每一个站都是一个节点。当你从家出发去公园玩时，你需要乘坐一条或多条线路，这些线路上的站点就形成了连接你出发点和目的地的路径（Path）。

On a subway map, every station is a vertex. For example, on Beijing Metro Line 1, "Tiananmen East Station," "Wangfujing Station," and "Dongdan Station" are all vertices. When you travel from home to the park, you need to take one or more lines, and the stations on these lines form a path connecting your starting point and destination.

而站点与站点之间的轨道连接就是边（Edge）。从“天安门东站”到“王府井站”有直接的轨道连接，这就是一条边；而从“天安门东站”到“东单站”，虽然它们都是一号线上的站点，但你必须经过“王府井站”才能到达，这也是图的一个重要特性——路径可能经过多个中间节点。

The track connections between stations are the edges. There is a direct track connection from "Tiananmen East Station" to "Wangfujing Station" — that's an edge. From "Tiananmen East Station" to "Dongdan Station," although they are both on Line 1, you must pass through "Wangfujing Station" to get there. This is also an important property of graphs — paths may pass through multiple intermediate vertices.

```mermaid graph LR A["家 Home"] --> B["天安门东<br>Tiananmen East"] B --> C["王府井<br>Wangfujing"] C --> D["东单<br>Dongdan"] D --> E["公园<br>Park"]

style A fill:#90EE90 style E fill:#90EE90 ```

看，上面这张简单的图展示了你从家出发，经过天安门东、王府井、东单，最后到达公园的路线。每一步之间的连接就是“边”，而每一个站点就是“节点”。

Look at the simple graph above, it shows your route from home, passing through Tiananmen East, Wangfujing, Dongdan, and finally arriving at the park. Each connection between steps is an "edge," and every station is a "vertex."

如果仔细研究地铁线路图，你会发现更多的“图”的特性。比如，有些线路是环形的，绕了一圈又回到起点；有些站点是换乘站，你可以在这里从一条线路换到另一条线路——这在图中叫做度（Degree）较大的节点，因为有更多的边在这里交汇。

If you study the subway map more carefully, you will discover more properties of "graphs." For instance, some lines form loops, returning to the starting point after a circle; some stations are transfer stations, where you can change from one line to another — in graphs, these are called vertices with high degree, because more edges converge there.

---

1.4 家族传承：家谱树也是图

1.4 Family Legacy: Family Trees are Also Graphs

除了社交网络和交通系统，还有一个你一定见过无数次的图——家谱图（Family Tree）！每逢春节回老家，墙上挂着的那个记录着爷爷奶奶、爸爸妈妈、叔叔阿姨的大幅照片和名字的图表，就是一张典型的图。

Besides social networks and transportation systems, there is another type of graph you must have seen countless times — the Family Tree! Every Spring Festival when you return to your hometown, the large chart on the wall recording photos and names of grandparents, parents, uncles, and aunts is a typical graph!

在家谱图中，节点代表家中的每一个人——你的爷爷、奶奶、爸爸、妈妈、你、你的兄弟姐妹，都是节点。而边代表的是家庭成员之间的血缘关系。爸爸和妈妈之间有一条边，表示他们是夫妻关系；你和爸爸之间有一条边，表示你是爸爸的孩子；你也有兄弟姐妹的话，你们之间也有一条边，表示你们是兄弟姐妹关系。

In a family tree, vertices represent every family member — your grandfather, grandmother, father, mother, you, and your siblings are all vertices. The edges represent blood relationships between family members. There is an edge between father and mother, indicating they are spouses; there is an edge between you and your father, indicating you are your father's child; if you have siblings, there is an edge between you, indicating sibling relationships.

```plantuml @startuml skinparam backgroundColor #FEFEFE skinparam defaultFontSize 16

rectangle "爷爷\nGrandfather" as GF rectangle "奶奶\nGrandmother" as GM rectangle "爸爸\nFather" as F rectangle "妈妈\nMother" as M rectangle "我\nMe" as ME rectangle "妹妹\nSister" as S

GF --> F : 父子 Father-Son GM --> F : 母子 Mother-Son GF --> M : 公婆 Parents-in-law GM --> M : 公婆 Parents-in-law F --> ME : 父子 Father-Child M