Тема занятия «Графы» и прежде, чем мы начнём. Заострим внимание на том, что мы будем проходить. Рассмотрим такое понятие как граф, что такое топология и какая именно топология бывает, а также при чем тут вообще энергетика.

Прежде чем переходить к определению граф, немножко поговорим о задачах. Есть такая задача о Кёнигсбергских мостах. Существует семь мостов, и мы хотим их все пройти, при этом не попасть на один мост дважды, и как же это сделать?


Наверное, мы начнём с того, что переберём вершины и поймём, что у нас ничего не получается и все равно пройдем где-то дважды.

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


Тогда что такое граф?

Граф — это некоторая математическая абстракция реальной системы любой природы и с использованием любых объектов, которые обладают парными связями.

Другими словами, граф — это совокупность множеств вершин и ребер. Вершины — это сами объекты и рёбра — это парные связи между объектами.

Математически граф можно представить следующим образом:


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


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


Но это ещё не все типы графов...

 

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

Задачу Коммивояжёра мы можем переформулировать таким образом: нам нужно найти минимальный простой цикл по всему графу, то есть мы должны за минимальное количество времени ресурсов обойти все вершины.

А как же все-таки искать такие циклы?

Нам в этом помогают алгоритмы, то есть мы можем перебирать все пути, мы можем использовать, например, жадный алгоритм или муравьиный алгоритм и прочее. Естественно, чем быстрее обрабатывает данные алгоритм, тем он выгоднее для нас.

Есть ещё такой тип задачи как задача о раскраске карт.

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


*в данной задаче нам необходимо использовать минимум три краски.

Существует такое понятие как гиперграф — это обобщение графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества множества вершин.


Для изучения графов важно знать понятие топологии. Топология — раздел математики, который является разновидностью геометрии, посвященный изучению качественных свойств геометрических фигур, не зависящих от расстояний, величин углов, площадей и объёмов.

Прежде всего говорим о топологии сети. Это такая конфигурация графа,
вершинам которого соответствуют конечные узлы сети (компьютеры и оборудование),
а рёбрам — физические или информационные связи между вершинами.

Сети бывают разные, мы можем рассматривать домашнюю сеть, это, например, электрическая сеть, где мы рассматриваем розетки, лампочки, выключатели и переключатели, которые подведены к главным щиткам.

Локальная сеть — это когда, есть какая-то одна большая подстанция и от неё мы ведём всех потребителей, в том числе заводы, обычные жилые дома, больницы и генераторы.

Есть ещё такой тип сетей, как магистральная сеть, допустим, когда от Калининграда до Владивостока протянута единая электрическая сеть ЛЭП (линия электропередач). С помощью нее регионы между собой перераспределяют электричество и используют совместно.

Но, как и у любого другого объекта у топологии есть некоторые требования:

  • Надёжность
  • Устойчивость
  • Скорость
  • Гибкость
  • Ресурсоёмкость

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

Устойчивая. Сеть планируется следующим образом, мы не должны все закидывать на одну подстанцию, должны быть альтернативные источники энергии, которые будут обеспечивать нас электричеством пока основная подстанция в ремонте. Нам нужно перераспределять и резервировать какую-то электроэнергию.

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

Суэцкий канал построили и время, за которое поставляются специй в Европу, стало меньше и стоимость товаров тоже упала.

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

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

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

Да, у каждой подстанции есть какие-то потребители и также должны быть предусмотрены альтернативные источники энергии, солнечные панели ветряные электростанции и также накопители.

А как это все понять?

Это все приходит через опыт, через какие-то эксперименты, через моделирование и через экспертные системы. На стенде ИЭС это все гораздо проще, в реальной жизни намного сложнее.

И о чем стоит задуматься?

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


Last modified: Tuesday, 2 September 2025, 11:54 AM