Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Эта статья о математической концепции. Для метода статистических представлений см. Линейный график .
Не путать с графом путей .

В математической дисциплине теории графов , то линейный график из неориентированного графа G представляет другой график L ( G ) , который представляет смежность между ребрами из G . L ( G ) строится следующим образом: для каждого ребра в G сделать вершину в L ( G ); для любых двух ребер в G, которые имеют общую вершину, сделайте ребро между соответствующими вершинами в L ( G ).

Линейный график имени взят из статьи Харари и Нормана (1960), хотя и Уитни (1932), и Краус (1943) использовали эту конструкцию до этого. [1] Другие термины, используемые для линейного графа, включают покрывающий граф , производную , дуальный от ребра к вершине , сопряженный , репрезентативный граф и ϑ-образ , [1], а также граф ребер , граф обмена , присоединенный граф и производный граф . [2]

Хасслер Уитни  ( 1932 ) доказал, что в одном исключительном случае структура связного графа G может быть полностью восстановлена ​​по его линейному графу. [3] Многие другие свойства линейных графов следуют путем перевода свойств нижележащего графа из вершин в ребра, и по теореме Уитни такой же перевод может быть выполнен и в другом направлении. Линейные графики когтя бесплатно и линейные графики двудольных графов являются идеальными . Линейные графики характеризуются девятью запрещенными подграфами и могут быть распознаны за линейное время .

Были изучены различные расширения концепции линейного графа, в том числе линейные графы линейных графов, линейные графы мультиграфов, линейные графы гиперграфов и линейные графики взвешенных графов.

Формальное определение [ править ]

Для графа G его линейный граф L ( G ) - это такой граф, что

  • каждая вершина из L ( G ) представляет собой ребро G ; и
  • две вершины L ( G ) являются смежными тогда и только тогда , когда их соответствующие ребра имеют общую конечную точку ( «падают») в G .

То есть это граф пересечения ребер G , представляющий каждое ребро набором двух его конечных точек. [2]

Пример [ править ]

На следующих рисунках показаны граф (слева, с синими вершинами) и его линейный граф (справа, с зелеными вершинами). Каждая вершина линейного графа помечена парой концов соответствующего ребра исходного графа. Например, зеленая вершина справа, помеченная 1,3, соответствует ребру слева между синими вершинами 1 и 3. Зеленая вершина 1,3 смежна с тремя другими зелеными вершинами: 1,4 и 1,2 (соответствующие к ребрам, разделяющим конечную точку 1 в синем графике) и 4,3 (соответствует ребру, разделяющему конечную точку 3 на синем графике).

  • График G

  • Вершины в L (G), построенные из ребер в G

  • Добавлены ребра в L (G)

  • Линейный график L (G)

Свойства [ править ]

Переведенные свойства нижележащего графа [ править ]

Свойства графа G, которые зависят только от смежности между ребрами, могут быть переведены в эквивалентные свойства в L ( G ), которые зависят от смежности между вершинами. Например, паросочетание в G - это набор ребер, ни одно из которых не является смежным, и соответствует набору вершин в L ( G ), ни одна из которых не является смежным, то есть независимому множеству . [4]

Таким образом,

  • Линейный график связного графа связан. Если G связен, он содержит путь, соединяющий любые два его ребра, который переводится в путь в L ( G ), содержащий любые две вершины L ( G ). Однако граф G , имеющий несколько изолированных вершин и поэтому несвязный, тем не менее может иметь связный линейный граф. [5]
  • Линейный граф имеет точку сочленения тогда и только тогда, когда базовый граф имеет мост, для которого ни одна конечная точка не имеет степени один. [2]
  • Для графа G с n вершинами и m ребрами количество вершин линейного графа L ( G ) равно m , а количество ребер L ( G ) равно половине суммы квадратов степеней вершин в G , минус м . [6]
  • Независимое множество в L ( G ) соответствует соответствия в G . В частности, максимальное независимое множество в L ( G ) соответствует максимальному соответствию в G . Поскольку максимальное сопоставление может быть найдено за полиномиальное время, то же самое можно сделать и с максимальными независимыми наборами линейных графов, несмотря на трудность задачи максимального независимого набора для более общих семейств графов. [4] Аналогично, радужные независимого множество в L ( G ) соответствует совпадению радуги в G .
  • Края хроматического число графы G равно вершина хроматического число ее линия графа L ( G ). [7]
  • Линейный граф реберно-транзитивного графа транзитивен по вершинам . Это свойство можно использовать для создания семейств графов, которые (например, граф Петерсена ) являются вершинно-транзитивными, но не являются графами Кэли : если G является реберно-транзитивным графом, который имеет не менее пяти вершин, не является двудольным и имеет нечетные вершины степени, то L ( G ) - вершинно-транзитивный граф не Кэли. [8]
  • Если граф G имеет цикл Эйлера , то есть если G связен и имеет четное число ребер в каждой вершине, то линейный граф G является гамильтоновым . Однако не все гамильтоновы циклы в линейных графах происходят из циклов Эйлера таким образом; например, линейный граф гамильтонова графа G сам является гамильтоновым, независимо от того, является ли G также эйлеровым. [9]
  • Если два простых графа изоморфны, то их линейные графы также изоморфны. Теорема Уитни изоморфизма графов обеспечивает обратную к этому для всех , кроме одной пары графов.
  • В контексте теории сложных сетей линейный граф случайной сети сохраняет многие свойства сети, такие как свойство малого мира (существование коротких путей между всеми парами вершин) и форму его распределения степеней . [10] Evans & Lambiotte (2009) отмечают, что любой метод поиска кластеров вершин в сложной сети можно применить к линейному графу и вместо этого использовать для кластеризации его ребер.

Теорема об изоморфизме Уитни [ править ]

Алмаз график , исключение сильной теоремы Уитни

Если линейные графы двух связных графов изоморфны, то лежащие в основе графы изоморфны, за исключением случая треугольного графа K 3 и когтя K 1,3 , которые имеют изоморфные линейные графы, но сами не изоморфны. [3]

Помимо K 3 и K 1,3 , существуют некоторые другие исключительные маленькие графы, линейный граф которых имеет более высокую степень симметрии, чем сам граф. Например, ромбовидный граф K 1,1,2 (два треугольника, разделяющих ребро) имеет четыре автоморфизма графа, но его линейный граф K 1,2,2их восемь. На иллюстрации показанного ромбовидного графа поворот графа на 90 градусов не является симметрией графа, а симметрией его линейного графа. Однако все такие исключительные случаи имеют не более четырех вершин. Усиленная версия теоремы об изоморфизме Уитни утверждает, что для связных графов с более чем четырьмя вершинами существует взаимно однозначное соответствие между изоморфизмами графов и изоморфизмами их линейных графов. [11]

Аналоги теоремы об изоморфизме Уитни доказаны для линейных графов мультиграфов , но в этом случае они более сложны. [12]

Сильно правильные и совершенные линейные графики [ править ]

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

Линейный граф полного графа K n также известен как треугольный граф , граф Джонсона J ( n , 2) или дополнение к графу Кнезера KG n , 2 . Треугольные графы характеризуются своими спектрами , за исключением n = 8. [13] Их также можно охарактеризовать (опять же, за исключением K 8 ) как сильно регулярные графы с параметрами srg ( n ( n  - 1) / 2, 2, 2 ( n  - 2), n  - 2, 4).[14] Три строго регулярных графа с теми же параметрами и спектром, что и L ( K 8 ), являются графами Чанга , которые могут быть получены переключением графа с L ( K 8 ).

Линия графы двудольного графа является совершенной (см теоремы Кёниги ), но не должны быть двудольным в качестве примера из когтя показывает график. Линейные графы двудольных графов образуют один из ключевых строительных блоков совершенных графов, используемых в доказательстве сильной теоремы о совершенных графах . [15] Частным случаем этих графов являются графы ладьи , линейные графы полных двудольных графов . Подобно линейным графам полных графов, они могут быть охарактеризованы, за одним исключением, количеством вершин, количеством ребер и количеством общих соседей для смежных и несмежных точек. Единственный исключительный случай - это L ( K4,4 ), который имеет общие параметры с графом Шриханде . Когда обе стороны двумерного разбиения имеют одинаковое количество вершин, эти графы снова становятся сильно регулярными. [16]

В более общем смысле, граф G называется совершенным по прямой, если L ( G ) идеальный граф . Линейные идеальные графы - это именно те графы, которые не содержат простых циклов нечетной длины больше трех. [17] Эквивалентно, граф является совершенным по прямой тогда и только тогда, когда каждая из его двусвязных компонент является либо двудольной, либо имеет форму K 4 (тетраэдр) или K 1,1, n (книга из одного или нескольких треугольников, имеющих общую общий край). [18] Каждый линейно совершенный граф сам совершенен. [19]

Другие связанные семейства графов [ править ]

Все линейные графы являются графами без клешней , графами без индуцированного подграфа в виде трехлистного дерева. [20] Как и в случае с графами без клешней в целом, каждый связный линейный граф L ( G ) с четным числом ребер имеет идеальное соответствие ; [21] эквивалентно, это означает, что если нижележащий граф G имеет четное число ребер, его ребра можно разбить на двухреберные пути.

Линейные графы деревьев - это в точности блочные графы без клешней . [22] Эти графы использовались для решения задачи в экстремальной теории графов , построения графа с заданным числом ребер и вершин, наибольшее дерево которого, индуцированное как подграф, является как можно меньшим. [23]

Все собственные значения по смежности матрицы из линейного графика, по крайней мере , -2. Причина этого заключается в том, что можно записать как , где - матрица беззнаковой инцидентности предстрочного графа, а - тождество. В частности, это матрица Грамиана системы векторов: все графы с этим свойством были названы обобщенными линейными графами. [24]

Характеристика и признание [ править ]

Разделение кликов [ править ]

Разбиение линейного графа на клики

Для произвольного графа G и произвольной вершины v в G множество ребер, инцидентных v, соответствует клике в линейном графе L ( G ). Образованные таким образом клики разбивают ребра L ( G ). Каждая вершина L ( G ) принадлежит ровно двум из них (двум кликам, соответствующим двум концам соответствующего ребра в G ).

Существование такого разбиения на клики может быть использовано для характеристики линейных графов: граф L является линейным графом некоторого другого графа или мультиграфа тогда и только тогда, когда можно найти набор клик в L (позволяя некоторым из клики быть одиночными вершинами), которые разбивают ребра L так , что каждая вершина L принадлежит ровно двум из клик. [20] Это будет линейный граф графа (а не мультиграфа), если этот набор клик удовлетворяет дополнительному условию, что никакие две вершины L не находятся в одних и тех же двух кликах. Для такого семейства клик основной граф G, для которого Lэто линейный график может быть восстановлен путем одной вершины в G для каждого клика, а ребро в G для каждой вершины в L с его конечными точками являются двумя кликами , содержащих вершину в L . Согласно сильной версии теоремы об изоморфизме Уитни, если базовый граф G имеет более четырех вершин, может быть только одно разбиение этого типа.

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

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

Запрещенные подграфы [ править ]

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

Другая характеристика линейных графиков была доказана в Beineke (1970) (и ранее без доказательства сообщалось Beineke (1968) ). Он показал, что существует девять минимальных графов, которые не являются линейными, так что любой граф, не являющийся линейным графом, имеет один из этих девяти графов в качестве индуцированного подграфа . То есть граф является линейным тогда и только тогда, когда никакое подмножество его вершин не индуцирует один из этих девяти графов. В приведенном выше примере четыре самые верхние вершины создают коготь (то есть полный двудольный граф K 1,3), показанный в верхнем левом углу иллюстрации запрещенных подграфов. Следовательно, согласно характеристике Бейнеке, этот пример не может быть линейным графиком. Для графов с минимальной степенью не ниже 5 для характеристики необходимы только шесть подграфов в левом и правом столбцах рисунка. [25]

Алгоритмы [ править ]

Руссопулос (1973) и Лехот (1974) описали алгоритмы линейного времени для распознавания линейных графов и восстановления их исходных графов. Сысло (1982) обобщил эти методы на ориентированные графы . Degiorgi и Simon (1995) описали эффективную структуру данных для поддержки динамического графа, подверженного вставкам и удалению вершин, и поддержания представления входных данных в виде линейного графа (если он существует) во времени, пропорциональном количеству измененных ребер в каждый шаг.

Алгоритмы Roussopoulos (1973) и Lehot (1974) основаны на характеризации линейных графов, включающих нечетные треугольники (треугольники в линейном графе со свойством, что существует другая вершина, смежная с нечетным числом вершин треугольника). Однако алгоритм Degiorgi & Simon (1995) использует только теорему об изоморфизме Уитни. Это усложняется необходимостью распознавания удалений, из-за которых оставшийся граф становится линейным графом, но при специализированной задаче статического распознавания необходимо выполнять только вставки, и алгоритм выполняет следующие шаги:

  • Постройте входной граф L , добавляя вершины по одной, на каждом шаге выбирая добавляемую вершину, смежную хотя бы с одной ранее добавленной вершиной. Добавляя вершины к L , поддерживайте граф G, для которого L  =  L ( G ); если алгоритму не удается найти подходящий граф G , то вход не является линейным графом, и алгоритм завершается.
  • При добавлении вершины v к графу L ( G ), для которого G имеет четыре или меньше вершин, может случиться так, что представление линейного графа не уникально. Но в этом случае расширенный граф достаточно мал, чтобы его представление в виде линейного графа можно было найти путем перебора за постоянное время.
  • При добавлении вершины V к большему графу L , что равняется линейным графиком другого графа G , пусть S будет подграфом G , образованный краями , которые соответствуют соседям V в L . Убедитесь, что у S есть вершинное покрытие, состоящее из одной или двух несмежных вершин. Если в покрытии две вершины, увеличьте G , добавив ребро (соответствующее v ), которое соединяет эти две вершины. Если в покрытии только одна вершина, то добавить в G новую вершину , смежную с этой вершиной.

Каждый шаг либо занимает постоянное время, либо включает поиск вершинного покрытия постоянного размера в графе S , размер которого пропорционален количеству соседей  v . Таким образом, общее время для всего алгоритма пропорционально сумме числа соседей всех вершин, которая (по лемме о подтверждении связи ) пропорциональна количеству входных ребер.

Итерация оператора линейного графика [ править ]

ван Рой и Вильф (1965) рассматривают последовательность графов

Они показывают, что, когда G - конечный связный граф , для этой последовательности возможны только четыре поведения:

  • Если G является циклом графа , то L ( G ) , и каждый последующий граф , в этой последовательности изоморфны к G самой. Это только связанные графики , для которых L ( G ) изоморфна G . [26]
  • Если G - клешня K 1,3 , то L ( G ) и все последующие графы в последовательности являются треугольниками.
  • Если G - граф путей, то каждый последующий граф в последовательности будет более коротким путем, пока в конечном итоге последовательность не завершится пустым графом .
  • Во всех остальных случаях размеры графов в этой последовательности со временем неограниченно увеличиваются.

Если G не подключен, эта классификация применяется отдельно к каждому компоненту G .

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

Обобщения [ править ]

Срединные графы и выпуклые многогранники [ править ]

Основная статья: Медиальный график

Когда планарный граф G имеет максимальную степень вершины три, его линейный граф является плоским, и каждое плоское вложение G может быть расширено до вложения L ( G ). Однако существуют плоские графы с более высокой степенью, линейные графы которых неплоские. К ним относятся, например, 5-звездочный K 1,5 , граф драгоценных камней, образованный добавлением двух непересекающихся диагоналей внутри правильного пятиугольника и всех выпуклых многогранников с вершиной четвертой или большей степени. [28]

Альтернативная конструкция, медиальный граф , совпадает с линейным графом для плоских графов с максимальной степенью три, но всегда плоская. У него те же вершины, что и у линейного графа, но потенциально меньше ребер: две вершины медиального графа смежны тогда и только тогда, когда соответствующие два ребра идут подряд на некоторой грани плоского вложения. Медиальный граф двойственного графа плоского графа такой же, как медиальный граф исходного плоского графа. [29]

Для правильных многогранников или простых многогранников операция медиального графа может быть представлена ​​геометрически операцией срезания каждой вершины многогранника плоскостью через середины всех его инцидентных ребер. [30] Эта операция называется вторым усечением, [31] вырожденным усечением, [32] или исправлением . [33]

Всего графиков [ править ]

Общий график Т ( G ) графа G имеет в качестве своих вершин элементов (вершин или ребер) G , и имеет ребро между двумя элементами , когда они являются либо происшествия или вблизи него . Полный граф также может быть получен путем подразделения каждого ребра G и затем взятия квадрата подразделенного графа. [34]

Мультиграфы [ править ]

Понятие линейного графа графа G естественным образом распространяется на случай, когда G - мультиграф. В этом случае характеристики этих графов можно упростить: характеризация в терминах разбиений клик больше не должна предотвращать принадлежность двух вершин к одной и той же клике, а характеристика запрещенными графами имеет семь запрещенных графов вместо девяти. [35]

Однако для мультиграфов существует большее количество пар неизоморфных графов, которые имеют одинаковые линейные графы. Например, полный двудольный граф K 1, n имеет тот же линейный граф, что и дипольный граф и мультиграф Шеннона с тем же числом ребер. Тем не менее в этом случае аналоги теоремы Уитни об изоморфизме еще можно вывести. [12]

Линейные орграфы[ редактировать ]

Построение графов де Брейна как итерированных линейных орграфов

Также возможно обобщить линейные графы на ориентированные графы. [36] Если G представляет собой ориентированный граф, его направлено линейный график или линии Орграф имеет одну вершину для каждого ребра G . Две вершины, представляющие направленные ребра от u до v и от w до x в G , соединяются ребром от uv до wx в линейном орграфе, когда v = w . То есть, каждое ребро в линии орграфа G представляет собой длину-два ориентированный путь в G . ВГрафы де Брейна могут быть сформированы путем повторения этого процесса формирования ориентированных линейных графов, начиная с полного ориентированного графа . [37]

Взвешенные линейные графики [ править ]

В линейном графе L ( G ) каждая вершина степени k в исходном графе G создает k ( k - 1) / 2 ребер в линейном графе. Для многих типов анализа это означает, что узлы высокой степени в G чрезмерно представлены в линейном графе L ( G ). Например, рассмотрим блуждание по вершинам исходного графа G . Это будет проходить по некоторому ребру e с некоторой частотой f . С другой стороны, это ребро e отображается в единственную вершину, скажем v , в линейном графе L( G ). Если теперь мы выполним тот же тип случайного блуждания по вершинам линейного графа, частота посещения v может полностью отличаться от f . Если наше ребро e в G было соединено с узлами степени O ( k ), оно будет проходить O ( k 2 ) чаще в линейном графе L ( G ). Другими словами, теорема об изоморфизме графов Уитни гарантирует, что линейный граф почти всегда кодирует топологию исходного графа Gчестно, но это не гарантирует, что динамика на этих двух графиках имеет простую взаимосвязь. Одно из решений - построить взвешенный линейный граф, то есть линейный граф со взвешенными ребрами . Для этого есть несколько естественных способов. [38] Например, если ребра d и e в графе G инцидентны в вершине v со степенью k , то в линейном графе L ( G ) ребру, соединяющему две вершины d и e, можно присвоить вес 1 / ( k - 1). Таким образом, каждое ребро в G(не предусмотрено ни конец соединен с вершиной степени 1) будет иметь силу 2 в линии граф L ( G ) , соответствующий двух концов , что ребро имеет в G . Это определение взвешенного линейного графа легко распространить на случаи, когда исходный граф G был направленным или даже взвешенным. [39] Принцип во всех случаях является обеспечение линии графа L ( G ) отражает динамику, а также топологию исходного графа G .

Линейные графики гиперграфов [ править ]

Основная статья: Линейный граф гиперграфа

Ребра гиперграфа могут образовывать произвольное семейство множеств , поэтому линейный граф гиперграфа такой же, как граф пересечений множеств из этого семейства.

Граф дизъюнктности [ править ]

Граф дизъюнктности группы G , обозначаемый D ( G ), строится следующим образом: для каждого ребра в G создайте вершину в D ( G ); для каждых двух ребер в G , у которых нет общей вершины, сделать ребро между их соответствующими вершинами в D ( G ). [40] Другими словами, D ( G ) - дополнительный граф к L ( G ). Клика в D ( G ) соответствует независимому множеству в L ( G ), и наоборот.

Примечания [ править ]

  1. ^ a b Хеммингер и Бейнеке (1978) , стр. 273.
  2. ^ a b c Harary (1972) , стр. 71.
  3. ^ а б Уитни (1932) ; Крауц (1943) ; Харари (1972) , теорема 8.3, с. 72. Харари дает упрощенное доказательство этой теоремы Юнгом (1966) .
  4. ^ a b Paschos, Vangelis Th. (2010), Комбинаторная оптимизация и теоретическая информатика: интерфейсы и перспективы , John Wiley & Sons, стр. 394, ISBN 9780470393673, Ясно, что существует взаимно однозначное соответствие между паросочетаниями графа и независимыми множествами его линейного графа.
  5. ^ На необходимость рассматривать изолированные вершины при рассмотрении связности линейных графов указывают Цветкович, Роулинсон и Симич (2004) , стр. 32 .
  6. ^ Харари (1972) , теорема 8.1, с. 72.
  7. ^ Дистель, Рейнхард (2006), Теория графов , Тексты для выпускников по математике, 173 , Springer, стр. 112, ISBN 9783540261834. Также в бесплатном онлайн-издании , Глава 5 («Раскраска»), с. 118.
  8. ^ Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы автоморфизмов и реконструкции графов , Студенческие тексты Лондонского математического общества, 54 , Кембридж: Издательство Кембриджского университета, стр. 44, ISBN 0-521-82151-7, MR  1971819. Лаури и Скапеллато приписывают этот результат Марку Уоткинсу.
  9. ^ Харари (1972) , теорема 8.8, стр. 80.
  10. ^ Ramezanpour, Karimipour & Mashaghi (2003) .
  11. ^ Юнг (1966) ; Дегиорги и Саймон (1995) .
  12. ^ а б Зверович (1997)
  13. ^ Ван Дам, Эдвин Р .; Хемерс, Виллем Х. (2003), "Какие графики определяются их спектром?" , Линейная алгебра и ее применения , 373 : 241-272, DOI : 10.1016 / S0024-3795 (03) 00483-X , МР 2022290 . См., В частности, предложение 8, с. 262.
  14. ^ Харари (1972) , теорема 8.6, с. 79. Харари приписывает этот результат независимым работам LC Chang (1959) и AJ Hoffman (1960).
  15. ↑ Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе» , Annals of Mathematics , 164 (1): 51–229, arXiv : math / 0212070 , doi : 10.4007 / annals.2006.164.51 , S2CID 119151552 . См. Также Roussel, F .; Rusu, I .; Thuillier, Х. (2009), "Сильная совершенный граф гипотеза: 40 лет попыток, а его разрешение", дискретная математика , 309 (20): 6092-6113, DOI : 10.1016 / j.disc.2009.05.024 , М.Р. 2552645 .
  16. ^ Харари (1972) , теорема 8.7, стр. 79. Харари приписывает эту характеристику линейных графов полных двудольных графов Муну и Хоффману. Случай равного числа вершин на обеих сторонах ранее был доказан Шриханде.
  17. ^ Троттер (1977) ; де Верра (1978) .
  18. ^ Maffray (1992) .
  19. ^ Троттер (1977) .
  20. ^ a b Harary (1972) , теорема 8.4, с. 74, дает три эквивалентные характеристики линейных графов: разбиение ребер на клики, свойство быть без когтей и нечетных алмазов и девять запрещенных графов Бейнеке.
  21. ^ Самнер, Дэвид П. (1974), "Графы с 1-факторов", Труды Американского математического общества , Американского математического общества, 42 (1): 8-12, DOI : 10,2307 / 2039666 , JSTOR 2039666 , MR 0323648  . Лас Вергнас, М. (1975), «Заметка о сопоставлениях в графах», Cahiers du Centre d'Etudes de Recherche Opérationnelle , 17 (2–3–4): 257–260, MR 0412042 .
  22. ^ Харари (1972) , теорема 8.5, стр. 78. Харари приписывает результат Гэри Чартранду .
  23. ^ Erdős, Пол ; Сакс, Майкл ; Сос, Вера Т. (1986), «Максимальные индуцированные деревья в графах», Журнал комбинаторной теории, серия B , 41 (1): 61–79, DOI : 10.1016 / 0095-8956 (86) 90028-6.
  24. ^ Cvetković, Роулинсон & Simić (2004) .
  25. ^ Метельский & Тышкевич (1997)
  26. ^ Этот результат также является теоремой 8.2 Харари (1972) .
  27. ^ Harary (1972) , теорема 8.11, стр. 81. Харари приписывает этот результат Гэри Чартранду .
  28. ^ Седлачек (1964) ; Гринвелл и Хеммингер (1972) .
  29. ^ Архидьякон, Dan (1992), "Медиальный граф и вольтамперная двойственность", дискретная математика , 104 (2): 111-141, DOI : 10.1016 / 0012-365X (92) 90328-D , МР 1172842 .
  30. ^ Макки, Т.А. (1989), "Теоретико-графическая модель географической двойственности", Комбинаторная математика: Труды Третьей Международной конференции (Нью-Йорк, 1985) , Ann. New York Acad. Sci., 555 , Нью-Йорк: New York Acad. Наук, С. 310-315,.. Bibcode : 1989NYASA.555..310M , DOI : 10.1111 / j.1749-6632.1989.tb22465.x , МР 1018637 .
  31. ^ Пью, Энтони (1976), Многогранники: визуальный подход , Калифорнийский университет Press, ISBN 9780520030565.
  32. Перейти ↑ Loeb, Arthur Lee (1991), Space Structures - their Harmony and Counterpoint (5-е изд.), Birkhäuser, ISBN 9783764335885.
  33. ^ Вайсштейн, Эрик В. «Исправление» . MathWorld .
  34. ^ Харари (1972) , стр. 82.
  35. ^ Ryjáček & Vrána (2011) .
  36. ^ Харари & Norman (1960) .
  37. ↑ Чжан и Линь (1987) .
  38. ^ Evans & Lambiotte (2009) .
  39. ^ Evans & Lambiotte (2010) .
  40. ^ Мешул, Рой (2001-01-01). «Кликовый комплекс и соответствие гиперграфа». Combinatorica . 21 (1): 89–94. DOI : 10.1007 / s004930170006 . ISSN 1439-6912 . S2CID 207006642 .  

Ссылки [ править ]

  • Beineke, LW (1968), "Производные графы орграфов", в Sachs, H .; Voss, H.-J .; Уолтер, Х.-Дж. (ред.), Beiträge zur Graphentheorie , Leipzig: Teubner, pp. 17–33..
  • Beineke, LW (1970), «Характеризация производных графов», Журнал комбинаторной теории , 9 (2): 129–135, DOI : 10.1016 / S0021-9800 (70) 80019-9 , MR  0262097.
  • Цветкович, Драгош; Роулинсон, Питер; Симич, Слободан (2004), Спектральные обобщения линейных графов , Серия лекций Лондонского математического общества, 314 , Кембридж: Издательство Кембриджского университета, DOI : 10.1017 / CBO9780511751752 , ISBN 0-521-83663-8, MR  2120511.
  • Degiorgi, Daniele Giorgio; Саймон, Клаус (1995), «Динамический алгоритм для распознавания линейных графов», Теоретико- графические концепции в информатике (Аахен, 1995) , Lecture Notes in Computer Science, 1017 , Berlin: Springer, pp. 37–48, doi : 10.1007 / 3-540-60618-1_64 , Руководство по ремонту  1400011.
  • Evans, TS; Lambiotte, R. (2009), «Линейные графики, разделение ссылок и перекрывающиеся сообщества», Physical Review E , 80 (1): 016105, arXiv : 0903.2181 , Bibcode : 2009PhRvE..80a6105E , doi : 10.1103 / PhysRevE.80.016105 , PMID  19658772.
  • Evans, TS; Lambiotte, R. (2010), «Линейные графики взвешенных сетей для перекрывающихся сообществ», European Physical Journal B , 77 (2): 265–272, arXiv : 0912.4389 , Bibcode : 2010EPJB ... 77..265E , doi : 10.1140 / epjb / e2010-00261-8 , S2CID  119504507.
  • Гринвелл, DL; Хеммингер, Роберт Л. (1972), «Запрещенные подграфы для графов с плоскими линейными графами», Дискретная математика , 2 : 31–34, DOI : 10.1016 / 0012-365X (72) 90058-1 , MR  0297604.
  • Harary, F .; Норман, Р.З. (1960), "Некоторые свойства линейных орграфов", Rendiconti del Circolo Matematico di Palermo , 9 (2): 161–169, doi : 10.1007 / BF02854581 , hdl : 10338.dmlcz / 128114 , S2CID  122473974.
  • Харари, Ф. (1972), «8. Линейные графы», теория графов (PDF) , Массачусетс: Addison-Wesley, стр. 71–83.
  • Hemminger, RL; Beineke, LW (1978), «Линейные графы и линейные орграфы», в Beineke, LW; Уилсон, Р.Дж. (ред.), Избранные темы теории графов , Academic Press Inc., стр. 271–305..
  • Юнг, HA (1966), "Zu Айнем Isomorphiesatz фон Х. Уитни für графена", Mathematische Annalen (на немецком языке ), 164 : 270-271, DOI : 10.1007 / BF01360250 , МР  0197353 , S2CID  119898359.
  • Краус, J. (1943), "Демонстрация новой теории Уитни сюр ле réseaux", Матем. Физ. Лапок , 50 : 75–85, MR  0018403.
  • Lehot, Филипп Х. (1974), "Алгоритм оптимальной для обнаружения график линии и выходной его корневой граф", Журнал АСМ , 21 (4): 569-575, DOI : 10,1145 / 321850,321853 , МР  0347690 , S2CID  15036484.
  • Маффре, Фредерик (1992), «Ядра в совершенных линейных графах», Журнал комбинаторной теории , серия B, 55 (1): 1–8, DOI : 10.1016 / 0095-8956 (92) 90028-V , MR  1159851.
  • Метельский, Юрий; Тышкевич, Регина (1997), "Линейные графы линейных 3-однородных гиперграфов", Журнал теории графов , 25 (4): 243–251, DOI : 10.1002 / (SICI) 1097-0118 (199708) 25: 4 < 243 :: AID-JGT1> 3.0.CO; 2-K.
  • Рамезанпур, А .; Каримипур, В .; Машаги, А. (2003), "Создание коррелированных сетей из некоррелированных" , Phys. Ред. E , 67 (4): 046107, arXiv : cond-mat / 0212469 , Bibcode : 2003PhRvE..67d6107R , doi : 10.1103 / Physreve.67.046107 , PMID  12786436 , S2CID  33054818.
  • ван Ройдж, ACM; Уилф, HS (1965), "Чередование график конечного графа", Acta Mathematica хунгарики , 16 (3-4): 263-269, DOI : 10.1007 / BF01904834 , ЛВП : 10338.dmlcz / 140421 , S2CID  122866512.
  • Руссопулос, Н.Д. (1973), « Алгоритм max { m , n } для определения графа H из его линейного графа G », Письма об обработке информации , 2 (4): 108–112, DOI : 10.1016 / 0020-0190 (73 ) 90029-X , Руководство по эксплуатации  0424435.
  • Рячек, Зденек; Vrána, Петр (2011), "Линейные графики мультиграфов и Гамильтона-связанности клешней свободных графов", Журнал теории графов , 66 (2): 152-173, DOI : 10.1002 / jgt.20498 , MR  2778727.
  • Седлачек, Й. (1964), "Некоторые свойства графов обмена", Теория графов и ее приложения (Proc. Sympos. Smolenice, 1963) , Publ. Дом Чехословацкой Акад. Sci., Прага, стр. 145–150, MR  0173255.
  • Сисло, Мацей М. (1982), "Алгоритм маркировки для распознавания линейного орграфа и вывода его корневого графа", Письма об обработке информации , 15 (1): 28–30, DOI : 10.1016 / 0020-0190 (82) 90080- 1 , Руководство по ремонту  0678028.
  • Trotter, LE, Jr. (1977), "Линейные совершенные графы", Математическое программирование , 12 (2): 255-259, DOI : 10.1007 / BF01593791 , MR  0457293 , S2CID  38906333.
  • де Werra, D. (1978), "О линейных совершенных графов", Математическое программирование , 15 (2): 236-238, DOI : 10.1007 / BF01609025 , MR  0509968 , S2CID  37062237.
  • Уитни, H. (1932), "Равные графики и связность графов", Американский журнал математики , 54 (1): 150-168, DOI : 10,2307 / 2371086 , ЛВП : 10338.dmlcz / 101067 , JSTOR  2371086.
  • Чжан, Фу Цзи; Линь, Го Нин (1987), "О графах де Брейна – Гуда", Acta Math. Синица , 30 (2): 195–205, MR  0891925.
  • Зверович, И. Э. (1997), Аналог теоремы Уитни для реберных графов мультиграфов и реберные мультиграфы, Дискретная математика (на русском), 9 (2): 98-105, DOI : 10,4213 / dm478 , МР  1468075. В переводе на английский как Зверович, И.. (1997), «Аналог теоремы Уитни для реберных графов мультиграфов и реберных мультиграфов», Дискретная математика и приложения , 7 (3): 287–294, doi : 10.1515 / dma.1997.7.3.287 , S2CID 120525090 .

Внешние ссылки [ править ]

  • Линейные графики , Информационная система о включениях классов графов
  • Вайсштейн, Эрик В. «Линейный график» . MathWorld .