ГРАФЫ

ЕГЭ-шный пример:

Вершины — это какие-то города:
A, B, C, D, E
Рёбра — это прямые дороги между городами:
(A,B), (A,C), (A,E), (B,D), (B,C), (C,D), (D,E)

❓Как можно отобразить граф?
▪️перечислением
▪️схемой
▪️матрицей смежности (связности)

В матрице (таблице): строка = откуда, столбец = куда, в ячейке = ребро.

📂 Чуть подробнее :

📝 Если у дороги есть длина — это вес ребра

Графы, у которых указан вес рёбер, называются «Взвешенные»
Подписываем числа для рёбер

📝 Если (А,B) = 42, например, то ведь (В,A) -— тоже?

Не всегда! Иногда есть ребро (А,B), но нет ребра (B,A) или их веса отличаются. Такие рёбра называются направленными, а граф направленным

‼️ Замечания:
▫️ Для ненаправленного графа — матрица связности симметрична: (А,B)=(B,A)
▫️Ребро (А,А) — называется петлёй и в ЕГЭ таких нет (главная диагональ матрицы всегда пустая).
▫️По матрице легко построить схему, а по схеме — матрицу.
▫️Для всего остального есть Вебиум и Касперский))