ЕГЭ-шный пример:
Вершины — это какие-то города:
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)
▫️Ребро (А,А) — называется петлёй и в ЕГЭ таких нет (главная диагональ матрицы всегда пустая).
▫️По матрице легко построить схему, а по схеме — матрицу.
▫️Для всего остального есть Вебиум и Касперский))
Авторизуйтесь, чтобы оставить комментарий.