Вершины
Ребра
Компоненты

Щелчок
  • Регулярный
  • Полный

Подробнее о теории графов

Песочница по теории графов

Граф — это набор точек, называемых вершинами, соединенных линиями, которые называются ребрами. Нарисуйте граф здесь в несколько щелчков, и песочница расскажет, что это за граф: из скольких компонент он состоит, является ли деревом, сколько цветов ему нужно как минимум, можно ли нарисовать его одним росчерком, и многое другое. Щелкните свойство, чтобы увидеть его на графе, измените ребро и посмотрите, как меняются ответы. Щелкните по пустому месту, чтобы добавить вершину. Щелкните вершину, а затем другую, чтобы соединить их ребром; повторите, чтобы удалить ребро. Перетащите вершину, чтобы переместить ее. Переключите щелчок на «Стирает» и щелкните вершину или ребро, чтобы удалить их. Когда вершина выбрана, Delete удаляет ее, а Esc снимает выделение. Щелкните свойство, чтобы показать его на графе. «Пример» загружает известный граф, «Случайный граф» создает новый, «Упорядочить» расставляет вершины свободнее, а «Дополнение» соединяет ровно те пары, которые не были соединены. Ctrl+Z отменяет шаг.

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

  1. Щелкните по пустому месту, чтобы добавить вершину. Щелкните вершину, а затем другую, чтобы соединить их; повторите, чтобы удалить ребро. Перетащите вершину, чтобы переместить ее.
  2. Посмотрите на свойства под графом и щелкните любое, чтобы показать его: раскраску, две доли, эйлеров путь, остовное дерево, кратчайший цикл или диаметр.
  3. Загрузите пример вроде графа Петерсена, создайте случайный граф, постройте дополнение или переключите щелчок на «Стирает», чтобы удалять вершины и ребра.

Что означают свойства

Степень вершины — это число ребер, выходящих из нее. Граф связен, если из любой вершины можно добраться до любой другой по ребрам, и является деревом, если он связен и не содержит циклов. Граф двудолен, если его вершины делятся на две доли так, что каждое ребро идет из одной доли в другую; это бывает ровно тогда, когда в нем нет циклов нечетной длины. Хроматическое число — наименьшее число цветов, при котором соседние вершины получают разные цвета. Длина кратчайшего цикла называется обхватом, а диаметр — это наибольшее расстояние между двумя вершинами, измеренное в ребрах.

Одним росчерком

Эйлеров путь проходит по каждому ребру ровно один раз. Леонард Эйлер в 1736 году на примере семи мостов Кёнигсберга понял, что этому мешает: каждый раз, проходя через вершину, путь использует два ее ребра. Поэтому либо все степени четные, и путь может закончиться там, где начался, либо ровно две степени нечетные, и путь должен идти из одной такой вершины в другую. Позже Карл Хирхольцер доказал, что этого условия вместе с требованием, чтобы все ребра лежали в одной компоненте, и достаточно. Загрузите пример с домиком и найдите, откуда нужно начинать росчерк.

Часто задаваемые вопросы

Что такое граф в теории графов?

Множество точек, называемых вершинами или узлами, и линий между некоторыми их парами, называемых ребрами. Это не график функции: граф описывает только то, что с чем соединено. Карты дорог, социальные сети, молекулы и компьютерные сети — все это графы.

Как вычисляется хроматическое число?

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

Когда в графе есть эйлеров путь?

Когда все его ребра лежат в одной компоненте и не более двух вершин имеют нечетную степень. Если нечетных вершин нет, существует эйлеров цикл, который заканчивается там, где начинается; если их две, каждый эйлеров путь начинается в одной из них и заканчивается в другой. Число нечетных вершин всегда четно, поэтому оно никогда не бывает равно одному.

Что такое дополнение графа?

Граф на тех же вершинах, ребрами которого служат ровно те пары, которые раньше не были соединены. Дополнение дополнения — это исходный граф. Например, дополнение графа Петерсена 6-регулярно, потому что каждая вершина была соединена с 3 из 9 остальных.

Чем знаменит граф Петерсена?

Это небольшой граф с 10 вершинами и 15 ребрами, который служит контрпримером ко многим правдоподобным гипотезам. Степень каждой вершины равна 3, длина кратчайшего цикла — 5, любые две вершины отстоят друг от друга не более чем на 2 ребра, и его нельзя нарисовать без пересечения ребер. С него песочница и начинается.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор