Граф (математика)

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

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

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

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

    Например, строение Википедии можно смоделировать при помощи ориентированного графа, в котором вершины — это статьи, а дуги (ориентированные рёбра) — гиперссылки (тематическая карта).

    Графы являются основным объектом изучения теории графов.

Источник: Википедия

Связанные понятия

В теории графов псевдолес — это неориентированный граф , в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес.
Кососимметрический граф — это ориентированный граф, который изоморфен своему собственному транспонированному графу, графу, образованному путём обращения всех дуг, с изоморфизмом, который является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.
В теории графов медианным графом называется неориентированный граф, в котором любые три вершины a, b, и c имеют единственную медиану — вершину m(a,b,c), которая принадлежит кратчайшим путям между каждой парой вершин a, b и c.

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

Упоминания в литературе

В нашей теории отбрасываем рисунки многогранников и оставляем только графы. Математика, описывающая квантовые состояния объема и площади, обеспечивает нас набором правил, указывающих, как линии могут соединять узлы и какие числа могут располагаться в различных местах диаграммы. Каждое квантовое состояние соответствует одному из графов, и каждому графу, удовлетворяющему правилам, соответствует квантовое состояние. Графы представляют собой удобную краткую запись возможных квантовых состояний пространства.
Сеть (network) – популярнейшее понятие системной биологии, повсеместно пронизывающее современную культуру, не только в рамках биологии или науки в целом[41]. В самом деле, трудно придумать более естественный способ представления связей между многочисленными объектами, чем сеть (в математике рассматриваемую как ориентированный или неориентированный граф). В биологическом контексте узлами (или иначе – вершинами) сети часто представляют гены или белки, а ребрами (связями между узлами) обозначают их взаимодействия, которые могут быть физическими, генетическими или регуляторными (Barabasi and Oltvai, 2004). К настоящему времени разработано множество методов описания и сравнения структур (топологий) сетей (табл. 4–1). Наиболее часто для анализа используется понятие функции распределения степеней вершин, где под степенью вершины понимают число ребер, связывающих эту вершину с другими. Сравнение таких функций, выполненное для сетей различного типа, показало принципиальное отличие биологических сетей (а также многих небиологических, включая Интернет) от случайных графов: случайные графы имеют колоколообразное распределение Пуассона, а для биологических сетей распределения описываются степенной функцией (табл. 4–1). Сети, имеющие степенные функции распределения степеней вершин, называют масштабно-инвариантными сетями, так как графики их функций внешне не меняются при масштабировании (обратите внимание на прямую линию в двойных логарифмических координатах на табл. 4–1). Такие сети всегда содержат небольшое число вершин с высокими степенями, так называемых хабов (hubs), и большое число слабосвязанных вершин.
В нетопологических ГИС цифруются пространственные объекты, изначально не знающие друг о друге, и построение отношений между ними осуществляется в режиме постпроцесса. В топологических же ГИС фиксация топологических пространственных отношений между объектами (смежности, связности, вложенности и др.) является основой их конструкции. Топологические системы являются более адекватным инструментом для создания цифровых карт, на основе которых можно производить различные аналитические и статистические операции. Топологические модели позволяют представить всю карту в виде графа. Площади, линии и точки описываются с помощью узлов и дуг. Каждая дуга идет от начального к конечному узлу. Известно, что находится справа и слева.
Элементов множество. Возьмем пример, что связи между элементами системы являются направленными по линии воздействия одного элемента на другой. Представим систему в виде ориентированного графа (рисунок 2), где элементы представлены вершинами, а связи между ними – дугами. Воздействующий элемент является предшествующим, и начало стрелки связи, идущей от него (начало дуги), – выходом этого элемента. Элемент, испытывающий воздействие, является последующим, и конец стрелки связи, поступающей в него (конец дуги), есть вход этого элемента. Частными случаями являются: взаимодействие двух элементов (b и d на рисунке 2 а), когда соединяющие две смежные вершины дуги образуют контур, и самосопряжение элемента, когда его выход возвращается на вход, т.е. образуется петля (с на рисунке 2а). У замкнутой системы элементы взаимодействуют лишь внутри системы. Для варианта незамкнутой системы такая однозначная идентификация невозможна. Здесь элементы могут быть отнесены либо к системе, либо к среде, т.е. к другой системе: вершина b на рисунке 2a стала входом х2' и выходом y2' на рисунке 2 в. В реальной действительности нет абсолютно обособленных систем, но пользоваться этой абстракцией удобно. Число связей, их направление и разветвленность являются структурными характеристиками системы.
Построение математических моделей привело к созданию особого вида топологий – индукторных пространств. В них происходит отказ от симметричного вхождения точек в окрестности друг друга. Это позволило сформулировать на едином языке многие факты и теоремы, которые ранее требовали различных формулировок для непрерывных метрических и топологических пространств, дискретных графов и структур (частичных порядков). Интересным классом пространств являются конические пространства, в которых топология аналогична пространству Г. Минковского (множество последовательных миров, где каждый отдельно взятый момент – это самостоятельная реальность), что удобно для волновых, релятивистских моделей. Конические пространства могут объяснить и существование анизотропного пространства. Было известно, что линейные автоморфизмы таких пространств образуют группу Лоренца, или аттрактор Лоренца (он же фрактал). Однако известны и нелинейные автоморфизмы. При размерностях пространства, начиная с трех, все автоморфизмы конических пространств линейны. Отсюда следует, в частности, что волновые процессы в пространстве определяют его линейную структуру, если размерность достаточно велика. На примере коллоидных и живых систем можно видеть их синхронную работу при формообразовании. Они формируют автоморфизм структур с микро– до мегауровня, и задают форму организмам. По всей вероятности, этот же механизм задействован в образовании и светового конуса при конденсации белка и в коллоидальных средах.

Связанные понятия (продолжение)

Перечислены связные 3-регулярные (кубические) простые графы с малым числом вершин.

Подробнее: Таблица простых кубических графов
st-Планарный граф — это биполярная ориентация планарного графа, для которого как источник, так и сток ориентации находятся на внешней грани графа. То есть это ориентированный граф, нарисованный без пересечений на плоскости таким образом, что не имеется ориентированных циклов в графе, точно одна вершина графа не имеет входных дуг, точно одна вершина графа не имеет исходящих дуг, и обе эти две специальные вершины лежат на внешней грани графа.
Граф Аполлония — это неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.
Биполярная ориентация или st-ориентация неориентированного графа — это назначение ориентации каждому ребру (ориентации), что превращает граф в направленный ациклический граф с единственным источником s и единственном стоком t, а st-нумерация графа — это топологическая сортировка полученного ориентированного ациклического графа.
Интервальный граф — граф пересечений мультимножества интервалов на прямой. Имеет по одной вершине для каждого интервала в множестве и по ребру между каждой парой вершин, если соответствующие интервалы пересекаются.
В теории графов мультиграфом (или псевдографом) называется граф, в котором разрешается присутствие кратных рёбер (их также называют «параллельными»), то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром (тем самым мультиграфы отличаются от гиперграфов, в которых каждое ребро может соединять любое число вершин, а не в точности две).

Подробнее: Мультиграф
Число пересечений графа — наименьшее число элементов в представлении данного графа как графа пересечений конечных множеств, или, эквивалентно, наименьшее число клик, необходимых для покрытия всех рёбер графа.
Кографы открывались независимо несколькими авторами, начиная с 1970-х годов. Самые ранние упоминания можно найти у Янга, Лерчса, Зайнше и Самнера. Эти графы назывались D*-графами, наследственными графами Дейси (после работы Джеймса Дейси об ортомодулярных решётках. Смотрите работу Самнера) и графы с двумя потомками Барлета и Ури.
В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.

Подробнее: Циркулянтный граф
В теории графов графами Пэли (названы в честь Раймонда Пэли) называются плотные неориентированные графы, построенные из членов подходящего конечного поля путём соединения пар элементов, отличающихся на квадратичный вычет. Графы Пэли образуют бесконечное семейство конференсных графов, поскольку тесно связаны с бесконечным семейством симметричных конференсных матриц. Графы Пэли дают возможность применить теоретические средства теории графов в теории квадратичных вычетов и имеют интересные свойства...

Подробнее: Граф Пэли
Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.
Косое разбиение графа — это разбиение его вершин на два подмножества, такое что порождённый подграф, образованный одним из его подмножеств вершин является несвязным, а другой порождённый подграф, образованный другим подмножеством является дополнением несвязного графа. Косые разбиения играют важную роль в теории совершенных графов.
Гамильто́нов граф — математический объект теории графов. Представляет собой граф (набор точек и соединяющих их линий), который содержит гамильтонов цикл. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу.
Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша, которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.
Дистанционно-регулярный граф — регулярный граф такой, что для любых двух вершин v и w число вершин с расстоянием j от v и расстоянием k от w зависят только от j, k и i = d(v, w).
Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломке Судоку. В этой области всё ещё ведутся активные исследования.
Говорят, что ориентированный граф апериодичен, если нет целого числа k > 1, делящего длину любого цикла графа. Эквивалентно, граф апериодичен, если наибольший общий делитель длин его циклов равен единице. Этот наибольший общий делитель для графа G называется периодом графа G.
Мост — ребро в теории графов, удаление которого увеличивает число компонент связности. Такие рёбра также известны как разрезающие рёбра, разрезающие дуги или перешейки. Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).

Подробнее: Граф без клешней
Куб Фибоначчи можно определить в терминах кодов Фибоначчи и расстояния Хэмминга, независимых множеств вершин в путях, или через дистрибутивные решётки.
Экстремальная теория графов — это ветвь теории графов. Экстремальная теория графов изучает экстремальные (максимальные или минимальные) свойства графов, удовлетворяющих определённым условиям. Экстремальность может относиться к различным инвариантам графов, таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа.
В теории графов граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду (ребро, соединяющее две вершины цикла, но не являющееся его частью).
Путевая ширина известна также как интервальная толщина (на единицу меньше размера наибольшей клики интервального суперграфа графа G), величина вершинного разделения или вершинно-поисковое число.
В теории графов нечётные графы On — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.

Подробнее: Нечётный граф
В теории графов паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.
Структурная теорема графов — это главный результат в области теории графов. Результат устанавливает глубокую и фундаментальную связь между теорией миноров графов и топологическими вложениями. Теорема была сформулирована в семнадцати статьях из серии из 23 статей Нейла Робертсона и Пола Сеймура. Доказательство теоремы очень длинно и запутано. Каварабайаши и Мохар и Ловаш провели обзор теоремы в доступном для неспециалистов виде, описав теорему и её следствия.
Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение. Другими словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа.
Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм...
В теории графов пороговый граф — это граф, который может быть построен из одновершинного графа последовательным выполнением следующих двух операций...
В теории графов говорят, что граф G гипогамильтонов, если сам по себе граф не имеет гамильтонова цикла, но любой граф, полученный удалением одной вершины из G, является гамильтоновым.

Подробнее: Гипогамильтонов граф
Разметка графа в математике — это назначение меток, которые традиционно представляются целыми числами, рёбрами, вершинами, или рёбрам, и вершинам графа.
Эйлеров цикл — эйлеров путь, являющийся циклом, то есть замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.
Восходящее планарное представление направленного ациклического графа — это вложение графа в евклидово пространство, в котором рёбра представлены как непересекающиеся монотонно возрастающие кривые. То есть, кривая, представляющая любое ребро, должна иметь свойство, что любая горизонтальная прямая пересекает его максимум в одной точке, и никакие два ребра не могут пересекаться, разве что на концах. В этом смысле это идеальный случай для послойного рисования графа, стиля представления графа, в котором...
В топологической теории графов 1-планарный граф — граф, который может быть нарисован в евклидовой плоскости таким образом, что каждое ребро имеет максимум одно пересечение с единственным другим ребром.
Фактор-критический граф (или почти сочетаемый граф .) — это граф с n вершинами, в котором каждый подграф с n − 1 вершинами имеет совершенное паросочетание. (Совершенное паросочетание в графе — это подмножество рёбер со свойством, что каждая из вершин графа является конечной вершиной в точности одного ребра из подмножества.)
В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом...

Подробнее: Корона (теория графов)
Гипотеза Эрдёша — Фабера — Ловаса — это нерешённая проблема о раскраске графов, названная именами Пала Эрдёша, Ванса Фабера и Ласло Ловаса, которые сформулировали её в 1972. Гипотеза гласит...
Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-Путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.
Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация.
В математике случайный граф — это общий термин для обозначения вероятностного распределения графов. Случайные графы можно описать просто распределением вероятности или случайным процессом, создающим эти графы. Теория случайных графов находится на стыке теории графов и теории вероятностей. С математической точки зрения случайные графы необходимы для ответа на вопрос о свойствах типичных графов. Случайные графы нашли практическое применение во всех областях, где нужно смоделировать сложные сети — известно...
Шарниром в теории графов называется вершина графа, при удалении которой количество компонент связности возрастает. Для обозначения этого понятия также используются термины «разделяющая вершина» и «точка сочленения».
Экспандеры — это класс графов, изучение которых первыми начали московские математики М. С. Пинскер, Л. А. Бассалыго и Г. А. Маргулис в семидесятые годы XX века.
Неравенство числа пересечений или лемма о пересечениях даёт нижнюю грань минимального числа пересечений данного графа как функцию от числа рёбер и вершин графа. Лемма утверждает, что для графов, у которых число рёбер e достаточно велико по сравнению с числом вершин n, число пересечений по меньшей мере пропорционально e3/n2.
Одновременное вложение графов — это техника визуализации двух и более различных графов на одном и том же множестве помеченных вершин, при которой избегается пересечения рёбер в каждом из графов. Пересечения между рёбрами разных графов разрешаются, не разрешается только пересечение рёбер одного графа.
В теории графов свободный от t-биклик граф — это граф, в котором нет полных двудольных графов с 2t вершинами Kt,t в качестве подграфов. Семейство графов является свободным от биклик, если существует число t, такое, что все графы в семействе свободны от t-биклик. Семейства свободных от бициклов графов образуют одно из наиболее общих типов семейств разреженных графов. Они возникают в задачах инцидентности в комбинаторной геометрии, а также используются в теории параметрической сложности.

Упоминания в литературе (продолжение)

На второй серии рисунков "Успешный поиск маршрута вывода на миварной сети" (рисунки 12 – 23) показано, как двое пользователей начинают поиск маршрута логического вывода: первый тянет сеть за входные данные, а второй – в другую сторону, за выходные (целевые показатели, объекты). Вследствие этого в процессе вывода задействуются только те объекты и правила, которые необходимы для данного поиска маршрута логического вывода. Таким образом удается избежать полного перебора с циклами и прочими неприятностями традиционных механизмов вывода, основанных на предикатах или графах. В случае существования маршрута вывода он быстро находится: пользователи его вытягивают в виде мостика и встречаются друг с другом, что отраженно смайликом.
К. Оберауэр с соавт. (Oberauer et al., 2003) предложили модель факторной структуры WMC, в которой рассматриваются три когнитивные функции: параллельная обработка и хранение, относительная интеграция (предварительно названная координацией) и наблюдение. Функция параллельной обработки и хранения соответствует общепринятому определению WMC. Она обычно оценивается с помощью сложных кратковременных задач, в которых участники должны запомнить множество пунктов за короткий период и выполнить обработку информации в промежутках между или после кодирования запоминаемых пунктов. Относительная интеграция определяется как способность строить новые связи между элементами и таким образом создавать структурные репрезентации (Waltz et al., 1999). Элементы могут храниться в памяти, но также могут быть даны перцептивно. Например, конструирование ментальной модели пространственного множества из некоторого описания (Byrne, Johnson-Laird, 1989), схватывание взаимоотношений из статистического графа (Halford et al., 2004) или «видение» созвездий в скоплении звезд и т. п. Наблюдение относится к контролю когнитивных процессов, включая репрезентацию цели, регулирование критериев ответов и изменение набора задач. Эти регуляторные процессы обычно относятся к категории исполнительных функций.
Если все показатели, приведенные в графах таблицы, выражены в одной и той же величине, то ее обозначение помещают после заголовка таблицы, через запятую или в скобках. Числовое значение показателя проставляют на уровне последней строки наименования, выравнивая по центру. Цифры в графах таблиц должны проставляться так, чтобы разряды чисел во всей графе были расположены один под другим, если они относятся к одному показателю. В графе должно быть соблюдено, как правило, одинаковое количество десятичных знаков для всех значений величин. Рекомендуется составлять таблицы, помещающиеся на одной странице. Если таблица не помещается на одной странице, то после заголовка добавляют строку, в которой графы нумеруют. В конце страницы таблицу прерывают, нижнюю горизонтальную линию не проводят. Оставшуюся часть таблицы переносят на другую страницу, перед ней помещают слова «Продолжение таблицы» с указанием номера, повторяют строку с нумерацией граф.
Таблицу с большим количеством столбцов (граф) можно разделять на части и размещать одну часть под другой на одной странице. При этом, если строки или графы выходят за формат страницы, в первом случае в каждой части повторяют заглавие (то есть названия столбцов), а во втором – боковую часть, то есть названия строк.
Таблицу с большим количеством граф можно разделять на части и размещать одну часть под другой на одной странице. При этом если строки или графы выходят за формат страницы, то в первом случае в каждой части повторяют заглавие, то есть названия столбцов, а во втором – боковую часть, то есть названия строк.
В первой графе таблицы указан порядковый номер круга; во второй – его площадь; в третьей графе – к какой руке прикладывалась фигура; во всех остальных – начальные буквы фамилий испытуемых и их показания (площадь изображения). Знаком «прав.» отмечены те пробы, при которых испытуемый точнее определял площадь круга правой рукой, знаком «лев.» – те, при которых площадь круга определялась точнее левой рукой, «сим.» обозначает, что показания правой и левой рук равны.
В графу «отметки поверхности земли» вписать отметки всех точек, лежащих на линии АВ (пересечения с горизонталями и характерные точки). Цифры следует располагать вертикально, точно против соответствующих ординат.
Аналогично, взаимодействию инь-ян квантов с внешним миром соответствуют графы на рисунке 24.
Каждая таблица должна иметь заголовок, кратко выражающий ее содержание. Графы, содержащие подлежащее, нумеруются заглавными буквами алфавита, а графы, содержащие сказуемое, – арабскими цифрами. Все слова в заголовках подлежащего и сказуемого должны писаться полностью. В необходимых случаях в заголовках граф нужно указывать единицу измерения показателя При отражении динамики показателей данные нужно располагать в хронологическом порядке.
Как бы сказал математик-дискранщик, узлы графа превращаются в рёбра, а рёбра в женщин. Сиречь в нервные узлы.
а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я