тема конспект графы 7 класс

Краткий ответ

Граф — это схема, состоящая из вершин и соединяющих их рёбер.
Вершины изображают объекты, а рёбра — связи между ними.

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

• Вершина — точка графа: \(A, B, C\).
• Ребро — линия, соединяющая две вершины: \(AB\).
• Смежные вершины — вершины, соединённые ребром.
• Степень вершины \(d(v)\) — количество рёбер, выходящих из вершины.
• Путь — последовательность вершин, соединённых рёбрами.
• Длина пути — количество рёбер в нём.
• Цикл — путь, который начинается и заканчивается в одной вершине.
• Связный граф — из любой вершины можно попасть в любую другую.
• Изолированная вершина — вершина без рёбер.

Виды графов

• Неориентированный граф — рёбра не имеют направления.
• Ориентированный граф — рёбра изображаются стрелками и имеют направление.
• Взвешенный граф — на рёбрах указаны значения, например расстояния или стоимость.

Как задают граф

1. Рисунком — вершины и линии между ними.
2. Списком рёбер:
   \[ AB,\ AC,\ BC \]
3. Списком смежности:
   \(A: B, C\) — из \(A\) идут рёбра к \(B\) и \(C\).
4. Матрицей смежности — таблицей, где \(1\) означает наличие ребра, а \(0\) — его отсутствие.

Для неориентированного графа матрица смежности симметрична относительно главной диагонали.

Пример

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

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

Тогда:

• \(d(A)=2\), потому что из \(A\) выходят \(AB\) и \(AC\);
• \(d(B)=2\);
• \(d(C)=3\);
• \(d(D)=1\).

Путь:

\[ A-B-C-D \]

Его длина равна \(3\), так как в нём три ребра.

Цикл:

\[ A-B-C-A \]

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

Важная проверка

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

\[ \sum d(v)=2m, \]

где \(m\) — число рёбер.

В примере:

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

Проверка выполнена верно.

Алгоритм решения задач:

1. Выписать все вершины и рёбра.
2. Для каждой вершины посчитать количество соединений.
3. Для поиска пути последовательно проверять рёбра между вершинами.
4. Результат проверить формулой \(\sum d(v)=2m\).

Дерево — это связный граф без циклов. Если в дереве \(n\) вершин, то рёбер всегда \(n-1\).