Графы

Редакция Без Сменки
Честно. Понятно. С душой.
📈 Граф = вершины + рёбра между вершинами

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

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

Где вы учитесь?

Вам также будет интересно

Даты «ПЕРЕСТРОЙКИ», которые ВАЖНО знать для ЕГЭ
Обязательно изучи этот материал, чтобы успешно сдать ЕГЭ по истории. Экономика 1985 – принятие курса на социально-экономическое УСКОРЕНИЕ страны...
Задний мозг
1️⃣ Мост — он располагается чуть выше продолговатого. Если вы морально готовы, то называйте его «варолиев мост» — это полное название. Он выполняет...
щелочные металлы
📍К щелочным металлам относятся металлы IA группы: Li, Na, K, Rb, Cs, Fr. 📍Характерная степень окисления в сложных соединения: +1 📚 Щелочные...
Математическая логика
Данная шпаргалка поможет разобраться с вопросами по теме «Математическая логика» в ЕГЭ по информатике. Здесь вы найдёте  понятное объяснение...
ЗАДАНИЕ 5 | климатические зоны России
IV тип — климатические зоны России   📜 Алгоритм решения: ① Определяем климатические пояса каждого пункта; ② Записываем ответ. 📖...
Покровная ткань
Что такое покровная ткань? Это слой (или несколько слоев) клеток, которые отделяют тело растения от окружающей среды 🧐 От сюда ясны функции этой...

0 комментария

Авторизуйтесь, чтобы оставить комментарий.