РусҚаз

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

Информатика · 10 класс · Графы и поиск пути · Урок 1 из 4

Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Что это

Представь схему метро: кружочки — станции, линии между ними — перегоны. Вот это и есть граф: набор вершин и рёбер, которые соединяют пары вершин. Графу неважно, где нарисован кружок, важно только, что с чем соединено.

Девушка-подросток стоит в вестибюле метро перед большой схемой линий и ведёт пальцем от станции к станции, вокруг спешат пассажиры.

Зачем это нужно

Графы спрятаны почти везде: в навигаторах и службах доставки, в маршрутах беспилотных дронов и складских роботов, в схемах электросетей и в сетях связи между серверами дата-центров. Нейросети, кстати, тоже рисуют как граф из узлов и связей, а молекулы новых лекарств и материалов химики описывают графом атомов. Через десять лет ИИ будет сам перебирать миллионы вариантов, но кто-то должен понять, что задачу вообще можно превратить в граф, что считать вершинами, что рёбрами и какие веса им дать. Человек, который умеет так смотреть на мир, сможет ставить задачи машинам и проверять, не ерунду ли они насчитали.

Инженер в светлом зале управления смотрит на огромный экран, где светящимися точками и линиями показана сеть городских дорог и движущихся по ней машин доставки.

Как это работает

Вершины — это объекты: станции, люди, веб-страницы, а рёбра — связи между ними. Если связь взаимная, как дружба, ребро рисуют простой линией, и граф называют неориентированным. Если связь идёт в одну сторону, как ссылка с одной страницы на другую, ребро рисуют стрелкой и называют дугой, а граф — ориентированным. Если на рёбрах написаны числа — минуты, километры или цена, — граф взвешенный. А степень вершины — это просто количество рёбер, которые к ней подходят; у стрелок отдельно считают входящие и исходящие.

Компания школьников сидит в кафе, у каждого телефон, а между ними натянуты разноцветные нитки, показывающие, кто с кем дружит.

Немного истории

Теорию графов начал великий математик Леонард Эйлер. Жители города Кёнигсберга спорили, можно ли пройти по всем семи мостам через реку, побывав на каждом ровно один раз. Эйлер заменил берега и острова точками, а мосты — линиями и доказал, что такой прогулки не существует: у слишком многих точек нечётное число линий. Так задачка про городскую прогулку стала первой задачей о графе.

Учёный восемнадцатого века в парике сидит за деревянным столом при свечах и рассматривает старинную карту города с рекой, островами и мостами.

Формула: сумма степеней

Посмотри на любое ребро: у него два конца, и каждый конец добавляет единичку к степени своей вершины. Значит, когда мы сложим степени всех вершин, каждое ребро посчитается ровно два раза. Отсюда формула: дэ один плюс дэ два плюс и так далее до дэ эн равно два умножить на е. Здесь дэ с номером — степень каждой вершины, эн — число вершин, а е — число рёбер; всё это просто количества, без единиц измерения. Добавишь в граф одно ребро — сумма степеней вырастет сразу на два. Например, в схеме метро девять рёбер, значит, сумма степеней всех станций равна восемнадцати.

  • d₁ + d₂ + … + dₙ = 2·Ed₁…dₙ — степени вершин, —
    n — число вершин, —
    E — число рёбер, —

Что будем делать на практике

А теперь давай попробуем выполнить практическое задание. Сейчас перед тобой граф «Метро»: семь станций и девять перегонов с минутами в пути — можешь потаскать вершины и убедиться, что граф от этого не меняется. Потом открой граф «Соцсеть» и найди человека, у которого больше всех друзей, то есть вершину с наибольшей степенью: аккуратно посчитай рёбра у каждой. В графе «Веб» нужна страница, на которую ведёт больше всего ссылок, поэтому там считай только входящие стрелки. Выбери вершину и нажми «Это ответ». Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.

Задание в опыте

В «Соцсети» найдите человека с наибольшей степенью (больше всех друзей), а в «Вебе» — страницу, на которую ведёт больше всего ссылок. Выберите вершину и нажмите «Это ответ».
Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Уроки темы: Графы и поиск пути

  1. Что такое граф
  2. Обход в ширину
  3. Алгоритм Дейкстры
  4. Графы вокруг нас