Лекция
Сразу хочу сказать, что здесь никакой воды про теория графов, и только нужная информация. Для того чтобы лучше понимать что такое теория графов, графы, граф , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..
теория
граф ов — это раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединенных ребрами. В строгом определении графом называется такая пара множеств 
, где 
есть подмножество любого счетного множества, а 
— подмножество 
.
В математике , теории графов являются изучением графиков , которые являются математическими структурами , используемых для моделирования попарных отношений между объектами. Граф в этом контексте состоит из вершин (также называемых узлами или точками ), которые соединены ребрами (также называемыми связями или линиями ). Различают неориентированные графы , где ребра соединяют две вершины симметрично, и ориентированные графы , где ребра связывают две вершины асимметрично; см. График (дискретная математика)для более подробных определений и других разновидностей обычно рассматриваемых типов графиков. Графы - один из основных объектов изучения дискретной математики .
Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как ребра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Теория графов содержит большое количество нерешенных проблем и пока не доказанных гипотез.
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кенигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Термин «граф» впервые ввел Сильвестр, Джеймс Джозеф в 1878 году в своей статье в Nature .
Проблема Кенигсбергского моста
Статья Леонарда Эйлера о семи мостах Кенигсберга, опубликованная в 1736 году, считается первой статьей в истории теории графов. [20] В этой статье, а также в статье, написанной Вандермондом по проблеме рыцаря , продолжался анализ места, инициированный Лейбницем . Изучена формула Эйлера , связывающее число ребер, вершин и граней выпуклого многогранника и обобщена Коши [21] и L'Huilier , [22] и представляет собой начало ветви математики известной как топологии .
Спустя более чем столетие после статьи Эйлера о мостах в Кенигсберге и пока Листинг вводил понятие топологии, Кэли руководствовался интересом к определенным аналитическим формам, возникающим из дифференциального исчисления, для изучения определенного класса графов - деревьев . [23] Это исследование имело большое значение для теоретической химии . Используемые им техники в основном касаются перечисления графов с определенными свойствами. Теория перечислительных графов возникла затем на основе результатов Кэли и фундаментальных результатов, опубликованных Полиа в период с 1935 по 1937 год. Они были обобщены Де Брейном.в 1959 году. Кэли связал свои результаты о деревьях с современными исследованиями химического состава. [24] Слияние идей из математики с идеями из химии положило начало тому, что стало частью стандартной терминологии теории графов.
В частности, термин «граф» был введен Сильвестром в статье, опубликованной в 1878 году в журнале Nature , где он проводит аналогию между «квантовыми инвариантами» и «ко-вариантами» алгебры и молекулярных диаграмм: [25]
«[…] Таким образом, каждый инвариант и ковариант становится выражаемым с помощью графа, в точности идентичного диаграмме Кекулеана или химикографу. […] Я даю правило геометрического умножения графов, то есть для построения графа из произведения не- или ко-варианты, чьи отдельные графики даны. […] »(курсив, как в оригинале).
Первый учебник по теории графов был написан Денесом Кенигом и опубликован в 1936 году. [26] Другая книга Фрэнка Харари , опубликованная в 1969 году, «считалась во всем мире окончательным учебником по этому предмету» [27] и позволили математикам, химикам, инженерам-электрикам и социологам общаться друг с другом. Харари пожертвовал все гонорары на финансирование премии Полиа . [28]
Одной из самых известных и стимулирующих проблем в теории графов является проблема четырех цветов : «Верно ли, что любая карта, нарисованная на плоскости, может иметь области, окрашенные в четыре цвета, таким образом, что любые две области, имеющие общую границу, имеют различные цвета?" Эта проблема была впервые поставлена Фрэнсисом Гатри в 1852 году, и первое письменное упоминание о ней содержится в письме Де Моргана, адресованном Гамильтону в том же году. Было предложено много неверных доказательств, в том числе Кэли, Кемпе и др. Исследование и обобщение этой проблемы Тейтом , Хивудом , Рэмси и Хадвигеромпривело к изучению раскрасок графов, вложенных на поверхности произвольного рода . Переформулировка Тейта породила новый класс проблем - проблемы факторизации , особенно изученные Петерсеном и Кенигом . Работы Рамсея по раскраске и, в частности, результаты, полученные Тураном в 1941 году, положили начало другой ветви теории графов, экстремальной теории графов .
Проблема четырех цветов оставалась нерешенной более века. В 1969 году Генрих Хееш опубликовал метод решения проблемы с помощью компьютеров. [29] Компьютерное доказательство, произведенное в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном, фундаментально использует понятие «разрядки», разработанное Хишем. [30] [31] Доказательство включало проверку свойств 1936 конфигураций на компьютере и не было полностью принято в то время из-за его сложности. Более простое доказательство, учитывающее только 633 конфигурации, было дано двадцатью годами позже Робертсоном , Сеймуром , Сандерсом и Томасом . [32]
Автономное развитие топологии с 1860 по 1930 годы способствовало развитию теории графов благодаря работам Джордана , Куратовски и Уитни . Еще одним важным фактором общего развития теории графов и топологии стало использование методов современной алгебры. Первым примером такого использования является работа физика Густава Кирхгофа , который опубликовал в 1845 году свои законы Кирхгофа для расчета напряжения и тока в электрических цепях .
Введение вероятностных методов в теорию графов, особенно в исследовании Эрдеша и Реньи асимптотической вероятности связности графов, дало начало еще одной ветви, известной как теория случайных графов , которая была плодотворным источником теоретических результатов.
Терминология теории графов поныне не определена строго. В частности, в монографии Гудман, Хидетниеми, 1981 сказано: «В программистском мире нет единого мнения о том, какой из двух терминов „граф“ или „сеть“. Мы выбрали термин „сеть“, так как он, по-видимому, чаще встречается в прикладных областях». Аналогичная ситуация с терминами «вершина/точка».
Виды графов:
Определения в теории графов различаются. Ниже приведены некоторые из основных способов определения графиков и связанных математических структур .
Граф с тремя вершинами и тремя ребрами.
В одном ограниченном , но очень общем смысле этого термина, граф является упорядоченная пара в составе:
, А набор из вершин (также называемые узлами или точки );
, А набор из ребер (также называемые ссылками или линией ), которые являются неупорядоченными парами вершин (то есть, ребро связанно с двумя различными вершинами).Чтобы избежать двусмысленности, этот тип объекта можно назвать именно неориентированным простым графом .
В краю 
, вершины 
и 
называются концами ребра. Говорят, что край соединяется x и и быть инцидентом на и дальше . Вершина может существовать в графе и не принадлежать ребру. Множественные ребра , недопустимые в соответствии с приведенным выше определением, - это два или более ребра, которые соединяют одни и те же две вершины.
В более общем смысле этого слова, допускающего наличие нескольких ребер, граф - это упорядоченная тройка 
в составе:
, А набор из вершин (также называемые узлами или точки );, А набор из ребер (называемая также ссылка или линия );
, функция инцидентности, отображающая каждое ребро в неупорядоченную пару вершин (то есть, ребро связано с двумя различными вершинами).Во избежание двусмысленности этот тип объекта можно назвать именно неориентированным мультиграфом .
Цикл является ребром , который соединяет вершину саму с собой. Графы, как это определено в двух определениях выше, не могут иметь циклов, потому что цикл, соединяющий вершину самому себе является ребром (для неориентированного простого графа) или инцидентно (для неориентированного мультиграфа) 
которого нет в 
. Поэтому, чтобы разрешить циклы, определения должны быть расширены. Для неориентированных простых графов определение следует изменить на 
. Для неориентированных мультиграфов определение 
следует изменить на 
. Чтобы избежать двусмысленности, эти типы объектов можно назвать неориентированными циклами разрешения простого графа и циклами разрешения неориентированного мультиграфа соответственно.
и обычно считаются конечными, и многие из хорошо известных результатов неверны (или сильно отличаются) для бесконечных графов, потому что многие из аргументов терпят неудачу в бесконечном случае . Более того, часто считается непустым, но может быть пустым набором. Порядок графа называется 
, его количество вершин. Размер графа называется 
, его количество ребер. Степень или валентность вершины есть число ребер, инцидентных к нему, где петля подсчитанных дважды.
В неориентированном простом графе порядка n максимальная степень каждой вершины равна n - 1, а максимальный размер графа равен n ( n - 1) / 2 .
Ребра неориентированного простого графа, допускающие петли 
индуцируют симметричное однородное отношение ~ на вершинах }что называется отношение смежности из . Конкретно для каждого ребра 
, его конечные точки и }называются смежными друг с другом, что обозначается ~ .
Направленный граф
Ориентированный граф с тремя вершинами и четырьмя направленными ребрами (двойная стрелка представляет ребро в каждом направлении).
Ориентированный граф или орграф представляет собой график , в котором ребра имеют ориентацию.
В одном ограниченном , но очень общем смысле этого термина, ориентированный граф является упорядоченной парой{\ Displaystyle G = (V, E)} в составе:
, А набор из вершин (также называемые узлами или точки );
, А набор из ребер (также называемые ориентированных ребер , направленные ссылки , направленные линии , стрелка или дуги ) , которые упорядоченные пары вершин (то есть, ребро связанно с двумя различными вершинами).Во избежание двусмысленности этот тип объекта можно назвать именно ориентированным простым графом .
В краю направлено из к , вершины и называются концами ребра,{\ displaystyle x}хвост края и }глава края. Об этом говорит сайт https://intellect.icu . Говорят, что край соединяется и быть инцидентом на и дальше . Вершина может существовать в графе и не принадлежать ребру. Край 
называется перевернутый край из . Множественные ребра , недопустимые в соответствии с приведенным выше определением, - это два или более ребра с одинаковым хвостом и одинаковой головой.
В более общем смысле этого слова, допускающего наличие нескольких ребер, ориентированный граф - это упорядоченная тройка в составе:
, А набор из вершин (также называемые узлами или точки );, А набор из ребер (также называемых ориентированных ребер , направленных ссылок , направленных линий , стрелок или дуг );
, функция инцидентности, отображающая каждое ребро в упорядоченную пару вершин (то есть ребро связано с двумя различными вершинами).Во избежание двусмысленности этот тип объекта можно назвать именно ориентированным мультиграфом .
Цикл является ребром , который соединяет вершину саму с собой. Направленные графы, как определено в двух определениях выше, не могут иметь циклов, потому что цикл, соединяющий вершину{\ displaystyle x} самому себе является ребром (для ориентированного простого графа) или инцидентно (для ориентированного мультиграфа) 
которого нет в 
. Поэтому, чтобы разрешить циклы, определения должны быть расширены. Для ориентированных простых графов определение следует изменить на 
. Для направленных мультиграфов определение{\ displaystyle \ phi} следует изменить на 
. Чтобы избежать двусмысленности, эти типы объектов можно назвать в точности ориентированным простым графом, разрешающим циклы, и ориентированным мультиграфом, разрешающим циклы (или колчаном ) соответственно.
Ребра ориентированного простого графа, допускающие петли является однородным отношением ~ на вершинах что называется отношение смежности из . Конкретно для каждого ребра{\ Displaystyle (х, у)}, его конечные точки и называются смежными друг с другом, что обозначается ~ .
Сетевой граф, сформированный редакторами Википедии (ребра), участвовавшими в различных языковых версиях Википедии (вершины) в течение одного месяца летом 2013 года.
Графы могут использоваться для моделирования многих типов отношений и процессов в физических, биологических, социальных и информационных системах. Многие практические задачи можно представить в виде графиков. Подчеркивая их применение к системам реального мира, термин сеть иногда определяется как обозначение графа, в котором атрибуты (например, имена) связаны с вершинами и ребрами, а субъект, который выражает и понимает системы реального мира как сеть. называется сетевой наукой .
В информатике графы используются для представления сетей связи, организации данных, вычислительных устройств, потока вычислений и т. Д. Например, ссылочная структура веб-сайта может быть представлена ориентированным графом, в котором вершины представляют веб-страницы. а направленные края представляют собой ссылки с одной страницы на другую. Аналогичный подход может быть применен к проблемам в социальных сетях , путешествиях, биологии, проектировании компьютерных микросхем, картировании прогрессирования нейродегенеративных заболеваний [10] [11] и многих других областях. Поэтому разработка алгоритмов для работы с графами представляет большой интерес для информатики. Трансформации графикичасто формализуется и представляется системами перезаписи графов . Дополнением к системам преобразования графов, ориентированным на манипулирование графами в памяти на основе правил, являются графовые базы данных, ориентированные на безопасное для транзакций , постоянное хранение и выполнение запросов к структурированным данным графа .
Теоретико-графические методы в различных формах оказались особенно полезными в лингвистике , поскольку естественный язык часто хорошо поддается дискретной структуре. Традиционно синтаксис и композиционная семантика следуют древовидным структурам, выразительная сила которых заключается в принципе композиционности , моделируемой в виде иерархического графа. Более современные подходы, такие как грамматика структуры фраз, управляемой заголовком, моделируют синтаксис естественного языка с использованием типизированных структур признаков , которые представляют собой направленные ациклические графы . В лексической семантикеособенно применительно к компьютерам, моделирование значения слова легче, когда данное слово понимается в терминах связанных слов; Поэтому семантические сети важны в компьютерной лингвистике . Тем не менее, другие методы в фонологии (например, теория оптимальности , которая использует решетчатые графы ) и морфологии (например, морфология конечного состояния, использующая преобразователи конечного состояния ) распространены при анализе языка как графа. Действительно, полезность этой области математики для лингвистики принесла такие организации, как TextGraphs , а также различные проекты «Сети», такие как WordNet , VerbNet и другие.
Теория графов также используется для изучения молекул в химии и физике . В физике конденсированного состояния трехмерная структура сложных смоделированных атомных структур может быть изучена количественно путем сбора статистических данных о свойствах теории графов, связанных с топологией атомов. Кроме того, « графики Фейнмана и правила вычислений резюмируют квантовую теорию поля в форме, тесно связанной с экспериментальными числами, которые каждый хочет понять». [12] В химии граф представляет собой естественную модель молекулы, где вершины представляют атомы, а реберные связи.. Этот подход особенно используется при компьютерной обработке молекулярных структур, от химических редакторов до поиска в базе данных. В статистической физике графики могут представлять локальные связи между взаимодействующими частями системы, а также динамику физического процесса в таких системах. Точно так же в вычислительной нейробиологииГрафы могут использоваться для представления функциональных связей между областями мозга, которые взаимодействуют, вызывая различные когнитивные процессы, где вершины представляют разные области мозга, а края представляют связи между этими областями. Теория графов играет важную роль в электрическом моделировании электрических сетей, здесь веса связаны с сопротивлением сегментов провода для получения электрических свойств сетевых структур. [13] Графики также используются для представления микромасштабных каналов пористой среды , в которых вершины представляют поры, а края представляют меньшие каналы, соединяющие поры. Теория химического графа использует молекулярный графкак средство моделирования молекул. Графики и сети - отличные модели для изучения и понимания фазовых переходов и критических явлений. Удаление узлов или ребер приводит к критическому переходу, когда сеть распадается на небольшие кластеры, что рассматривается как фазовый переход. Этот пробой изучается с помощью теории перколяции. [14] [15]
Теория графов в социологии: Социограмма Морено (1953). [16]
Теория графов также широко используется в социологии как способ, например, для измерения престижа действующих лиц или изучения распространения слухов , в частности, с помощью программного обеспечения для анализа социальных сетей . Под эгидой социальных сетей существует множество различных типов графиков. [17] Графики знакомств и дружбы показывают, знают ли люди друг друга. Графики влияния моделируют, могут ли одни люди влиять на поведение других. Наконец, графики сотрудничества моделируют, работают ли два человека вместе определенным образом, например, вместе снимаются в кино.
Аналогичным образом, теория графов полезна в биологии и усилиях по сохранению, где вершина может представлять регионы, где существуют (или населяют) определенные виды, а края представляют собой пути миграции или перемещения между регионами. Эта информация важна при изучении моделей размножения или отслеживании распространения болезней, паразитов или того, как изменения в перемещении могут повлиять на другие виды.
Графы также обычно используются в молекулярной биологии и геномике для моделирования и анализа наборов данных со сложными взаимосвязями. Например, графические методы часто используются для «кластеризации» клеток в типы клеток при анализе транскриптома отдельной клетки . Другое использование - моделирование генов или белков в пути и изучение взаимосвязей между ними, таких как метаболические пути и сети регуляции генов [18]. Эволюционные деревья, экологические сети и иерархическая кластеризация паттернов экспрессии генов также представлены в виде структур графов. Методы, основанные на графах, широко используются исследователями в некоторых областях биологии, и они станут гораздо более распространенными по мере развития технологий, позволяющих использовать такого рода многомерные данные.
Теория графов также используется в коннектомике ; [19] нервную систему можно рассматривать как граф, где узлы - нейроны, а ребра - связи между ними.
В математике графики полезны в геометрии и некоторых частях топологии, таких как теория узлов . Алгебраическая теория графов тесно связана с теорией групп . Алгебраическая теория графов применялась во многих областях, включая динамические системы и сложность.
Структуру графа можно расширить, присвоив вес каждому ребру графа. Графики с весами или взвешенные графы используются для представления структур, в которых попарные связи имеют некоторые числовые значения. Например, если график представляет дорожную сеть, веса могут представлять длину каждой дороги. С каждым ребром может быть связано несколько весов, включая расстояние (как в предыдущем примере), время в пути или денежные затраты. Такие взвешенные графики обычно используются для программирования GPS и поисковых систем планирования путешествий, которые сравнивают время полета и стоимость.
Графы представляются визуально путем рисования точки или круга для каждой вершины и рисования линии между двумя вершинами, если они соединены ребром. Если график направлен, направление указывается стрелкой.
Рисование графа не следует путать с самим графиком (абстрактной, невизуальной структурой), так как существует несколько способов структурировать чертеж графика. Все, что имеет значение, это то, какие вершины связаны с другими по количеству ребер, а не точное расположение. На практике часто бывает трудно решить, представляют ли два рисунка один и тот же график. В зависимости от проблемной области некоторые схемы могут быть лучше подходящими и более понятными, чем другие.
Новаторская работа В. Т. Тутте оказала большое влияние на тему рисования графиков. Среди других достижений он представил использование методов линейной алгебры для получения чертежей графов.
Можно также сказать, что рисование графа охватывает проблемы, связанные с числом пересечений и его различными обобщениями. Число пересечений графа - это минимальное количество пересечений между ребрами, которое должен содержать рисунок графа на плоскости. Для плоского графа число пересечений по определению равно нулю.
Также изучаются рисунки на поверхностях, отличных от плоскости.
Есть разные способы хранения графиков в компьютерной системе. Используемая структура данных зависит как от структуры графа, так и от алгоритма, используемого для управления графом. Теоретически можно различать структуры списков и матриц, но в конкретных приложениях лучшая структура часто представляет собой комбинацию обоих. Структуры списков часто предпочтительнее для разреженных графов, поскольку они требуют меньшего объема памяти. С другой стороны, матричные структуры обеспечивают более быстрый доступ для некоторых приложений, но могут потреблять огромные объемы памяти. Реализации разреженных матричных структур, которые эффективны на современных параллельных компьютерных архитектурах, являются объектом текущего исследования. [33]
Структуры списков включают в себя список инцидентности , массив пар вершин и список смежности , в котором отдельно перечислены соседи каждой вершины: подобно списку инцидентности, каждая вершина имеет список вершин, с которыми она смежна.
Матричные структуры включают матрицу инцидентности , матрицу нулей и единиц, строки которой представляют вершины, а столбцы - ребра, и матрицу смежности , в которой как строки, так и столбцы индексируются по вершинам. В обоих случаях 1 указывает на два соседних объекта, а 0 указывает на два несмежных объекта. Степень матрицы показывает степень вершин. Лапласиане матрица представляет собой модифицированную форму матрицы смежности , которая включает в себя информацию о степени вершин, и полезно в некоторых расчетах , таких как теорема Кирхгофа о числе остовных деревьев графа. Матрица расстоянийкак и матрица смежности, строки и столбцы индексируются по вершинам, но вместо того, чтобы содержать 0 или 1 в каждой ячейке, она содержит длину кратчайшего пути между двумя вершинами.
Существует обширная литература по графическому перечислению : проблема подсчета графов, удовлетворяющих заданным условиям. Некоторые из этих работ можно найти у Харари и Палмера (1973).
Распространенная проблема, называемая проблемой изоморфизма подграфов , заключается в нахождении фиксированного графа как подграфа в данном графе. Одна из причин , чтобы быть заинтересованы в таком вопросе является то , что многие свойства графов являются наследственными для подграфов, что означает , что граф обладает свойством тогда и только тогда , когда все подграфов есть это тоже. К сожалению, поиск максимальных подграфов определенного типа часто является NP-полной проблемой . Например:
Одним из частных случаев изоморфизма подграфов является проблема изоморфизма графов . Он спрашивает, изоморфны ли два графа. Неизвестно, является ли эта проблема NP-полной и может ли она быть решена за полиномиальное время.
Аналогичная проблема - найти индуцированные подграфы в данном графе. Опять же, некоторые важные свойства графа являются наследственными по отношению к индуцированным подграфам, что означает, что граф обладает свойством тогда и только тогда, когда все индуцированные подграфы также имеют его. Нахождение максимальных индуцированных подграфов определенного типа также часто бывает NP-полным. Например:
Еще одна такая проблема, второстепенная проблема сдерживания, состоит в том, чтобы найти фиксированный граф как второстепенный для данного графа. Незначительный или subcontraction графа является любым графиком , полученным путем принятия подграфа и заражения некоторые (или нет) ребер. Многие свойства графа являются наследственными для миноров, что означает, что граф обладает свойством тогда и только тогда, когда оно есть у всех миноров. Например, теорема Вагнера гласит:
Похожая проблема, проблема сдерживания подразделений, состоит в том, чтобы найти фиксированный граф как подразделение данного графа. Подразделение или Гомеоморфизм графа является любой график , полученный путем разделения некоторых (или нет) ребер. Включение подразделения связано с такими свойствами графа, как плоскостность . Например, теорема Куратовского гласит:
Еще одна проблема сдерживания подразделений - это гипотеза Кельмана – Сеймура :
Другой класс проблем связан с тем, в какой степени различные виды и обобщения графов определяются их подграфами с удаленными точками . Например:
Многие проблемы и теоремы теории графов связаны с различными способами раскраски графов. Обычно нужно раскрасить граф так, чтобы никакие две соседние вершины не были одного цвета, или с другими подобными ограничениями. Можно также рассмотреть раскраску ребер (возможно, чтобы никакие два совпадающих ребра не были одного цвета) или другие варианты. Среди известных результатов и гипотез о раскраске графов можно выделить следующие:
Теории моделирования ограничений относятся к семействам ориентированных графов, связанных частичным порядком . В этих приложениях графики упорядочены по специфичности, что означает, что более ограниченные графы - которые более конкретны и, следовательно, содержат больший объем информации - относятся к более общим. Операции между графами включают оценку направления отношения подчинения между двумя графами, если они есть, и вычисление объединения графов. Объединение двух графов аргументов определяется как наиболее общий граф (или его вычисление), который согласуется с входными данными (т. Е. Содержит всю информацию), если такой граф существует; известны эффективные алгоритмы унификации.
Для структур ограничений, которые являются строго композиционными , объединение графов является достаточной функцией выполнимости и комбинирования. Хорошо известные приложения включают автоматическое доказательство теорем и моделирование разработки языковой структуры .
Существует множество проблем, возникающих, в частности, из приложений, связанных с различными представлениями о потоках в сетях , например:
Проблемы покрытия в графах могут относиться к различным задачам покрытия множества на подмножествах вершин / подграфов.
Декомпозиция, определяемая как разбиение множества ребер графа (с необходимым числом вершин, сопровождающих ребра каждой части разбиения), вызывает широкий круг вопросов. Часто требуется разбить граф на подграфы, изоморфные фиксированному графу; например, разложение полного графа на гамильтоновы циклы. Другие задачи определяют семейство графов, на которое следует разложить данный граф, например, семейство циклов, или разложение полного графа K n на n - 1 заданное дерево, имеющее соответственно 1, 2, 3, ... , n - 1 ребро.
Некоторые конкретные проблемы декомпозиции, которые были изучены, включают:
Многие проблемы связаны с описанием членов различных классов графов. Ниже приведены некоторые примеры таких вопросов:
При изображении графов на рисунках чаще всего используется следующая система обозначений: вершины графа изображаются точками или, при конкретизации смысла вершины, прямоугольниками, овалами и др., где внутри фигуры раскрывается смысл вершины (графы блок-схем алгоритмов). Если между вершинами существует ребро, то соответствующие точки (фигуры) соединяются линией или дугой. В случае ориентированного графа дуги заменяют стрелками, они явно указывают направленность ребра. Иногда рядом с ребром размещают поясняющие надписи, раскрывающие смысл ребра, например, в графах переходов конечных автоматов. Различают планарные и не планарные графы. Планарный граф — это граф, который можно изобразить на рисунке (плоскости) без пересечения ребер (простейшие — треугольник или пара связанных вершин), иначе граф не планарный. В том случае, если граф не содержит циклов (содержащих, по крайней мере, один путь однократного обхода ребер и вершин с возвратом в исходную вершину), его принято называть «деревом». Важные виды деревьев в теории графов — бинарные деревья, где каждая вершина имеет одно входящее ребро и ровно два выходящих, или является конечной — не имеющей выходящих ребер и содержит одну корневую вершину, в которую нет входящего ребра.
Не следует путать изображение графа собственно с графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены ребрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет (другими словами, изоморфны ли соответствующие изображениям графы). В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.
К теории графов также относится целый ряд математических проблем, не решенных на сегодняшний день.
А как ты думаешь, при улучшении теория графов, будет лучше нам? Надеюсь, что теперь ты понял что такое теория графов, графы, граф и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.
Комментарии
Оставить комментарий
Дискретная математика. Теория множеств . Теория графов . Комбинаторика.
Термины: Дискретная математика. Теория множеств . Теория графов . Комбинаторика.