Конспект: «Графы», 7 класс

1. Что такое граф

Граф — это модель, состоящая из:

• вершин — точек графа;
• рёбер — линий, соединяющих вершины.

Например, города можно представить вершинами, а дороги между ними — рёбрами.

Обозначают граф так:

\[ G=(V,E), \]

где \(V\) — множество вершин, \(E\) — множество рёбер.

---

2. Основные понятия

Вершина

Точка графа. Вершины обычно обозначают буквами или числами:

\[ A,\ B,\ C,\ 1,\ 2,\ 3. \]

Ребро

Соединяет две вершины. Ребро между \(A\) и \(B\) записывают:

\[ AB. \]

Степень вершины

Степень вершины — количество рёбер, выходящих из неё.

Например, если вершина соединена с тремя другими вершинами, её степень равна \(3\).

Обозначение:

\[ \deg(A)=3. \]

---

3. Виды графов

Неориентированный граф

Рёбра не имеют направления. По ребру можно двигаться в обе стороны.

\[ A-B \]

Ориентированный граф

Рёбра имеют направление. Их называют дугами.

\[ A\rightarrow B \]

Из \(A\) можно попасть в \(B\), но не обязательно наоборот.

Взвешенный граф

У каждого ребра указано число — его вес. Например, расстояние или стоимость дороги.

---

4. Путь и цикл

Путь

Путь — последовательность вершин, соединённых рёбрами.

Например:

\[ A-B-C-D. \]

Длина пути — количество рёбер в нём. Путь \(A-B-C-D\) имеет длину \(3\).

Цикл

Цикл — путь, который начинается и заканчивается в одной вершине:

\[ A-B-C-A. \]

---

5. Связный граф

Граф называется связным, если из любой его вершины можно попасть в любую другую, двигаясь по рёбрам.

Если некоторые вершины изолированы или отделены от остальных, граф несвязный.

---

6. Дерево

Дерево — это связный граф, в котором нет циклов.

Свойства дерева:

• между любыми двумя вершинами существует ровно один путь;
• если в дереве \(n\) вершин, то рёбер:

\[ n-1. \]

Например, в дереве с 6 вершинами будет:

\[ 6-1=5 \]

рёбер.

---

7. Способы задания графа

Рисунок

Вершины изображают точками, рёбра — линиями.

Список рёбер

Перечисляют пары соединённых вершин:

\[ AB,\ AC,\ BC,\ CD. \]

Таблица смежности

В таблице указывают, какие вершины соединены.

Для графа с рёбрами \(AB\), \(AC\), \(BC\), \(CD\):

	A	B	C	D
A	0	1	1	0
B	1	0	1	0
C	1	1	0	1
D	0	0	1	0

Число \(1\) означает наличие ребра, а \(0\) — его отсутствие.

---

8. Важное свойство степеней вершин

Сумма степеней всех вершин равна удвоенному числу рёбер:

\[ \deg(v_1)+\deg(v_2)+\ldots+\deg(v_n)=2E, \]

где \(E\) — количество рёбер.

Например, если в графе 5 рёбер, сумма степеней всех вершин равна:

\[ 2\cdot5=10. \]

---

9. Пример

Пусть граф имеет рёбра:

\[ AB,\ AC,\ BC,\ CD. \]

Тогда:

• \(\deg(A)=2\);
• \(\deg(B)=2\);
• \(\deg(C)=3\);
• \(\deg(D)=1\);
• путь \(A-B-C-D\) имеет длину \(3\);
• \(A-B-C-A\) — цикл;
• граф связный;
• всего 4 вершины и 4 ребра.

Проверка:

\[ 2+2+3+1=8=2\cdot4. \]

Главное запомнить

Граф = вершины + рёбра.
Степень вершины = число рёбер, связанных с ней.
Путь — движение по рёбрам, цикл — замкнутый путь.
Дерево — связный граф без циклов.