Лекция
Это окончание невероятной информации про теория графов.
...
быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров углеводородов и других органических соединений.
Теория графов также используется для изучения молекул в химии и физике . В физике конденсированного состояния трехмерная структура сложных смоделированных атомных структур может быть изучена количественно путем сбора статистических данных о свойствах теории графов, связанных с топологией атомов. Кроме того, « графы Фейнмана и правила вычислений резюмируют квантовую теорию поля в форме, тесно связанной с экспериментальными числами, которые каждый хочет понять». В химии граф представляет собой естественную модель молекулы, где вершины представляют атомы, а реберные связи.. Этот подход особенно используется при компьютерной обработке молекулярных структур, от химических редакторов до поиска в базе данных. В статистической физике графы могут представлять локальные связи между взаимодействующими частями системы, а также динамику физического процесса в таких системах. Точно так же в вычислительной нейробиологииГрафы могут использоваться для представления функциональных связей между областями мозга, которые взаимодействуют, вызывая различные когнитивные процессы, где вершины представляют разные области мозга, а края представляют связи между этими областями. Теория графов играет важную роль в электрическом моделировании электрических сетей, здесь веса связаны с сопротивлением сегментов провода для получения электрических свойств сетевых структур. Графы также используются для представления микромасштабных каналов пористой среды , в которых вершины представляют поры, а края представляют меньшие каналы, соединяющие поры. Теория химического графа использует молекулярный графкак средство моделирования молекул. Графы и сети - отличные модели для изучения и понимания фазовых переходов и критических явлений. Удаление узлов или ребер приводит к критическому переходу, когда сеть распадается на небольшие кластеры, что рассматривается как фазовый переход. Этот пробой изучается с помощью теории перколяции.
Теория графов в социологии: Социограмма Морено (1953).
Теория графов также широко используется в социологии как способ, например, для измерения престижа действующих лиц или изучения распространения слухов , в частности, с помощью программного обеспечения для анализа социальных сетей . Под эгидой социальных сетей существует множество различных типов графы. Графы знакомств и дружбы показывают, знают ли люди друг друга. Графы влияния моделируют, могут ли одни люди влиять на поведение других. Наконец, графы сотрудничества моделируют, работают ли два человека вместе определенным образом, например, вместе снимаются в кино.
Аналогичным образом, теория графов полезна в биологии и усилиях по сохранению, где вершина может представлять регионы, где существуют (или населяют) определенные виды, а края представляют собой пути миграции или перемещения между регионами. Эта информация важна при изучении моделей размножения или отслеживании распространения болезней, паразитов или того, как изменения в перемещении могут повлиять на другие виды.
Графы также обычно используются в молекулярной биологии и геномике для моделирования и анализа наборов данных со сложными взаимосвязями. Например, графические методы часто используются для «кластеризации» клеток в типы клеток при анализе транскриптома отдельной клетки . Другое использование - моделирование генов или белков в пути и изучение взаимосвязей между ними, таких как метаболические пути и сети регуляции генов . Эволюционные деревья, экологические сети и иерархическая кластеризация паттернов экспрессии генов также представлены в виде структур графов. Методы, основанные на графах, широко используются исследователями в некоторых областях биологии, и они станут гораздо более распространенными по мере развития технологий, позволяющих использовать такого рода многомерные данные.
Теория графов также используется в коннектомике ; нервную систему можно рассматривать как граф, где узлы - нейроны, а ребра - связи между ними.
В математике графы полезны в геометрии и некоторых частях топологии, таких как теория узлов . Алгебраическая теория графов тесно связана с теорией групп . Алгебраическая теория графов применялась во многих областях, включая динамические системы и сложность.
В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете. Посик минимального пути для обезда заданных городов
Схематехника, микроэлектроника
Структуру графа можно расширить, присвоив вес каждому ребру графа. Графы с весами или взвешенные графы используются для представления структур, в которых попарные связи имеют некоторые числовые значения. Например, если граф представляет дорожную сеть, веса могут представлять длину каждой дороги. С каждым ребром может быть связано несколько весов, включая расстояние (как в предыдущем примере), время в пути или денежные затраты. Такие взвешенные графы обычно используются для программирования GPS и поисковых систем планирования путешествий, которые сравнивают время полета и стоимость.
Графы представляются визуально путем рисования точки или круга для каждой вершины и рисования линии между двумя вершинами, если они соединены ребром. Если граф направлен, направление указывается стрелкой.
Рисование графа не следует путать с самим графом (абстрактной, невизуальной структурой), так как существует несколько способов структурировать чертеж графа. Все, что имеет значение, это то, какие вершины связаны с другими по количеству ребер, а не точное расположение. На практике часто бывает трудно решить, представляют ли два рисунка один и тот же граф. В зависимости от проблемной области некоторые схемы могут быть лучше подходящими и более понятными, чем другие.
Новаторская работа В. Т. Тутте оказала большое влияние на тему рисования графом. Среди других достижений он представил использование методов линейной алгебры для получения чертежей графов.
Можно также сказать, что рисование графа охватывает проблемы, связанные с числом пересечений и его различными обобщениями. Число пересечений графа - это минимальное количество пересечений между ребрами, которое должен содержать рисунок графа на плоскости. Для плоского графа число пересечений по определению равно нулю.
Также изучаются рисунки на поверхностях, отличных от плоскости.
Есть разные способы хранения графов в компьютерной системе. Используемая структура данных зависит как от структуры графа, так и от алгоритма, используемого для управления графом. Теоретически можно различать структуры списков и матриц, но в конкретных приложениях лучшая структура часто представляет собой комбинацию обоих. Структуры списков часто предпочтительнее для разреженных графов, поскольку они требуют меньшего объема памяти. С другой стороны, матричные структуры обеспечивают более быстрый доступ для некоторых приложений, но могут потреблять огромные объемы памяти. Реализации разреженных матричных структур, которые эффективны на современных параллельных компьютерных архитектурах, являются объектом текущего исследования.
Структуры списков включают в себя список инцидентности , массив пар вершин и список смежности , в котором отдельно перечислены соседи каждой вершины: подобно списку инцидентности, каждая вершина имеет список вершин, с которыми она смежна.
Матричные структуры включают матрицу инцидентности , матрицу нулей и единиц, строки которой представляют вершины, а столбцы - ребра, и матрицу смежности , в которой как строки, так и столбцы индексируются по вершинам. В обоих случаях 1 указывает на два соседних объекта, а 0 указывает на два несмежных объекта. Степень матрицы показывает степень вершин. Лапласиане матрица представляет собой модифицированную форму матрицы смежности , которая включает в себя информацию о степени вершин, и полезно в некоторых расчетах , таких как теорема Кирхгофа о числе остовных деревьев графа. Матрица расстоянийкак и матрица смежности, строки и столбцы индексируются по вершинам, но вместо того, чтобы содержать 0 или 1 в каждой ячейке, она содержит длину кратчайшего пути между двумя вершинами.
Существует обширная литература по графическому перечислению : проблема подсчета графов, удовлетворяющих заданным условиям. Некоторые из этих работ можно найти у Харари и Палмера (1973).
Распространенная проблема, называемая проблемой изоморфизма подграфов , заключается в нахождении фиксированного графа как подграфа в данном графе. Одна из причин , чтобы быть заинтересованы в таком вопросе является то , что многие свойства графов являются наследственными для подграфов, что означает , что граф обладает свойством тогда и только тогда , когда все подграфов есть это тоже. К сожалению, поиск максимальных подграфов определенного типа часто является NP-полной проблемой . Например:
Одним из частных случаев изоморфизма подграфов является проблема изоморфизма графов . Он спрашивает, изоморфны ли два графа. Неизвестно, является ли эта проблема NP-полной и может ли она быть решена за полиномиальное время.
Аналогичная проблема - найти индуцированные подграфы в данном графе. Опять же, некоторые важные свойства графа являются наследственными по отношению к индуцированным подграфам, что означает, что граф обладает свойством тогда и только тогда, когда все индуцированные подграфы также имеют его. Нахождение максимальных индуцированных подграфов определенного типа также часто бывает NP-полным. Например:
Еще одна такая проблема, второстепенная проблема сдерживания, состоит в том, чтобы найти фиксированный граф как второстепенный для данного графа. Незначительный или subcontraction графа является любым графа , полученным путем принятия подграфа и заражения некоторые (или нет) ребер. Многие свойства графа являются наследственными для миноров, что означает, что граф обладает свойством тогда и только тогда, когда оно есть у всех миноров. Например, теорема Вагнера гласит:
Похожая проблема, проблема сдерживания подразделений, состоит в том, чтобы найти фиксированный граф как подразделение данного графа. Подразделение или Гомеоморфизм графа является любой граф , полученный путем разделения некоторых (или нет) ребер. Включение подразделения связано с такими свойствами графа, как плоскостность . Например, теорема Куратовского гласит:
Еще одна проблема сдерживания подразделений - это гипотеза Кельмана – Сеймура :
Другой класс проблем связан с тем, в какой степени различные виды и обобщения графов определяются их подграфами с удаленными точками . Например:
Многие проблемы и теоремы теории графов связаны с различными способами раскраски графов. Обычно нужно раскрасить граф так, чтобы никакие две соседние вершины не были одного цвета, или с другими подобными ограничениями. Можно также рассмотреть раскраску ребер (возможно, чтобы никакие два совпадающих ребра не были одного цвета) или другие варианты. Среди известных результатов и гипотез о раскраске графов можно выделить следующие:
Теории моделирования ограничений относятся к семействам ориентированных графов, связанных частичным порядком . В этих применениях граф упорядочены по специфичности, что означает, что более ограниченные графы - которые более конкретны и, следовательно, содержат больший объем информации - относятся к более общим. Операции между графами включают оценку направления отношения подчинения между двумя графами, если они есть, и вычисление объединения графов. Объединение двух графов аргументов определяется как наиболее общий граф (или его вычисление), который согласуется с входными данными (т. е. Содержит всю информацию), если такой граф существует; известны эффективные алгоритмы унификации.
Для структур ограничений, которые являются строго композиционными , объединение графов является достаточной функцией выполнимости и комбинирования. Хорошо известные приложения включают автоматическое доказательство теорем и моделирование разработки языковой структуры .
Существует множество проблем, возникающих, в частности, из приложений, связанных с различными представлениями о потоках в сетях , например:
Проблемы покрытия в графах могут относиться к различным задачам покрытия множества на подмножествах вершин / подграфов.
Декомпозиция, определяемая как разбиение множества ребер графа (с необходимым числом вершин, сопровождающих ребра каждой части разбиения), вызывает широкий круг вопросов. Часто требуется разбить граф на подграфы, изоморфные фиксированному графу; например, разложение полного графа на гамильтоновы циклы. Другие задачи определяют семейство графов, на которое следует разложить данный граф, например, семейство циклов, или разложение полного графа K n на n - 1 заданное дерево, имеющее соответственно 1, 2, 3, ... , n - 1 ребро.
Некоторые конкретные проблемы декомпозиции, которые были изучены, включают:
Многие проблемы связаны с описанием членов различных классов графов. Ниже приведены некоторые примеры таких вопросов:
При изображении графов на рисунках чаще всего используется следующая система обозначений: вершины графа изображаются точками или, при конкретизации смысла вершины, прямоугольниками, овалами и др., где внутри фигуры раскрывается смысл вершины (графы блок-схем алгоритмов). Если между вершинами существует ребро, то соответствующие точки (фигуры) соединяются линией или дугой. В случае ориентированного графа дуги заменяют стрелками, они явно указывают направленность ребра. Иногда рядом с ребром размещают поясняющие надписи, раскрывающие смысл ребра, например, в графах переходов конечных автоматов. Различают планарные и не планарные графы. Планарный граф — это граф, который можно изобразить на рисунке (плоскости) без пересечения ребер (простейшие — треугольник или пара связанных вершин), иначе граф не планарный. В том случае, если граф не содержит циклов (содержащих, по крайней мере, один путь однократного обхода ребер и вершин с возвратом в исходную вершину), его принято называть «деревом». Важные виды деревьев в теории графов — бинарные деревья, где каждая вершина имеет одно входящее ребро и ровно два выходящих, или является конечной — не имеющей выходящих ребер и содержит одну корневую вершину, в которую нет входящего ребра.
Не следует путать изображение графа собственно с графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены ребрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет (другими словами, изоморфны ли соответствующие изображениям графы). В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.
К теории графов также относится целый ряд математических проблем, не решенных на сегодняшний день.
А как ты думаешь, при улучшении теория графов, будет лучше нам? Надеюсь, что теперь ты понял что такое теория графов, графы, граф, способы описания графов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.
Часть 1 Граф, Теория графов, история, классификация, описание, применение
Часть 2 - Граф, Теория графов, история, классификация, описание, применение
Комментарии
Оставить комментарий
Дискретная математика. Теория множеств . Теория графов . Комбинаторика.
Термины: Дискретная математика. Теория множеств . Теория графов . Комбинаторика.