Линейный график

Граф, представляющий ребра другого графа

В математической дисциплине теории графов линейный граф неориентированного графа 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 на синем графике).

• 
  График Ж
• 
  Вершины в 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 ) равно половине суммы квадратов степеней вершин в Г , минус м . ^[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] Эванс и Ламбиотт (2009) отмечают, что любой метод поиска кластеров вершин в сложной сети может быть применен к линейному графу и вместо этого использован для кластеризации его ребер.

Теорема Уитни об изоморфизме

Ромбовидный график (слева) и его более симметричный линейный график (справа), исключение из сильной теоремы Уитни.

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

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

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

Сильно регулярные и идеальные линейные графики

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

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

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

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

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

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

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

Все собственные значения матрицы смежности A линейного графа не меньше −2. Причина этого в том, что A можно записать как , где J — беззнаковая матрица инцидентности графа перед строкой, а I — единица. В частности, A + 2 I — матрица Грама системы векторов: все графы с этим свойством называются обобщенными линейными графами. ^[24] ${\displaystyle A=J^{\mathsf {T}}J-2I}$

Характеристика и признание

Раздел клика

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

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

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

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

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

Запрещенные подграфы

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

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

Алгоритмы

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

Алгоритмы Руссопулоса (1973) и Лего (1974) основаны на характеристиках линейных графов, включающих нечетные треугольники (треугольники в линейном графе со свойством, что существует еще одна вершина, смежная с нечетным числом вершин треугольника). Однако алгоритм Дегиорджи и Саймона (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) рассматривают последовательность графов

${\displaystyle G,L(G),L(L(G)),L(L(L(G))),\dots .\ }$

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

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

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

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

Обобщения

Медиальные графы и выпуклые многогранники

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

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

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

Всего графиков

Полный граф T ( 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 ) , то в линейном графе L ( G ) оно будет проходиться O ( k2 ) ^чаще . Другими словами, теорема об изоморфизме графа Уитни гарантирует, что линейный граф почти всегда точно кодирует топологию исходного графа 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. Хеммингер и Бейнеке (1978), стр. 273.
2. Харари (1972), с. 71.
3. Уитни (1932); Крауш (1943); Харари (1972), теорема 8.3, с. 72. Харари дает упрощенное доказательство этой теоремы Юнга (1966).
4. Пасхос, Вангелис Т. (2010), Комбинаторная оптимизация и теоретическая информатика: интерфейсы и перспективы, John Wiley & Sons, стр. 394, ISBN 9780470393673Очевидно , что существует взаимно однозначное соответствие между паросочетаниями графа и независимыми множествами его линейного графа.
5. На необходимость учитывать изолированные вершины при рассмотрении связности линейных графов указывают Цветкович, Роулинсон и Симич (2004), с. 32.
6. Харари (1972), Теорема 8.1, с. 72.
7. Дистель, Рейнхард (2006), Теория графов, Тексты для выпускников по математике, том. 173, Спрингер, с. 112, ISBN 9783540261834. Также в бесплатном онлайн-издании, глава 5 («Раскраска»), с. 118.
8. Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы автоморфизмов и реконструкции графов, Студенческие тексты Лондонского математического общества, том. 54, Кембридж: Издательство Кембриджского университета, стр. 54. 44, ISBN 0-521-82151-7, г-н  1971819. Лаури и Скапеллато приписывают этот результат Марку Уоткинсу.
9. Харари (1972), Теорема 8.8, с. 80.
10. Рамезанпур, Каримипур и Машаги (2003).
11. Юнг (1966); Дегиорджи и Саймон (1995).
12. Зверович (1997)
13. Ван Дам, Эдвин Р.; Хемерс, Виллем Х. (2003), «Какие графы определяются их спектром?», Линейная алгебра и ее приложения , 373 : 241–272, doi : 10.1016/S0024-3795(03)00483-X , MR  2022290, S2CID  32070167. См., в частности, предложение 8, с. 262.
14. Харари (1972), Теорема 8.6, с. 79. Харари приписывает этот результат независимым работам Л.С. Чанга (1959) и А.Дж. Хоффмана (1960).
15. Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе», Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi : 10.4007/annals.2006.164.51, S2CID  119151552. См. также Руссель Ф.; Русу, И.; Тюилье, Х. (2009), «Гипотеза о сильном совершенном графе: 40 лет попыток и ее решение», Discrete Mathematics , 309 (20): 6092–6113, doi : 10.1016/j.disc.2009.05.024 , MR  2552645, S2CID  16049392.
16. Харари (1972), Теорема 8.7, с. 79. Харари приписывает эту характеристику линейных графов полных двудольных графов Муну и Хоффману. Случай равного числа вершин с обеих сторон ранее был доказан Шрикханде.
17. Троттер (1977); де Верра (1978).
18. Маффрей (1992).
19. Троттер (1977).
20. Харари (1972), теорема 8.4, с. 74, дает три эквивалентные характеристики линейных графов: разбиение ребер на клики, свойство отсутствия когтей и отсутствия нечетных ромбов и девять запрещенных графов Бейнеке.
21. Самнер, Дэвид П. (1974), «Графики с 1-факторами», Труды Американского математического общества , Американское математическое общество, 42 (1): 8–12, doi : 10.2307/2039666, JSTOR  2039666, MR  0323648. Лас Верньяс, М. (1975), «Заметки о сопоставлениях в графах», Cahiers du Center d'Etudes de Recherche Opérationnelle , 17 (2–3–4): 257–260, MR  0412042.
22. Харари (1972), Теорема 8.5, с. 78. Харари приписывает результат Гэри Чартранду .
23. Эрдеш, Пол ; Сакс, Майкл ; Сос, Вера Т. (1986), «Максимально индуцированные деревья в графах», Журнал комбинаторной теории, серия B , 41 (1): 61–79, doi : 10.1016/0095-8956(86)90028-6.
24. Цветкович, Роулинсон и Симич (2004).
25. Метельский и Тышкевич (1997)
26. Этот результат также является теоремой 8.2 Харари (1972).
27. Харари (1972), Теорема 8.11, с. 81. Харари приписывает этот результат Гэри Чартранду .
28. Седлачек (1964); Гринвелл и Хеммингер (1972).
29. Архидиакон, Дэн (1992), «Медиальный график и двойственность напряжения и тока», Discrete Mathematics , 104 (2): 111–141, doi : 10.1016/0012-365X(92)90328-D , MR  1172842.
30. Макки, Т. А. (1989), «Теоретико-графовая модель географической двойственности», Комбинаторная математика: материалы Третьей международной конференции (Нью-Йорк, 1985) , Ann. Нью-Йоркская академия. наук., вып. 555, Нью-Йорк: Нью-Йоркская академия. Sci., стр. 310–315, Bibcode : 1989NYASA.555..310M, doi : 10.1111/j.1749-6632.1989.tb22465.x, MR  1018637, S2CID  86300941..
31. Пью, Энтони (1976), Многогранники: визуальный подход , University of California Press, ISBN 9780520030565.
32. Леб, Артур Ли (1991), Космические структуры - их гармония и контрапункт (5-е изд.), Birkhäuser, ISBN 9783764335885.
33. Вайсштейн, Эрик В. «Исправление». Математический мир .
34. Харари (1972), с. 82.
35. Риячек и Врана (2011).
36. Харари и Норман (1960).
37. Чжан и Линь (1987).
38. Эванс и Ламбьотт (2009).
39. Эванс и Ламбьотт (2010).
40. Мешулам, Рой (1 января 2001 г.). «Комплекс клик и сопоставление гиперграфов». Комбинаторика . 21 (1): 89–94. дои : 10.1007/s004930170006. ISSN  1439-6912. S2CID  207006642.

Рекомендации

• Бейнеке, Л.В. (1968), «Производные графы орграфов», Сакс, Х.; Восс, Х.-Дж.; Вальтер, Х.-Дж. (ред.), Beiträge zur Graphentheorie , Лейпциг: Тойбнер, стр. 17–33..
• Бейнеке, Л.В. (1970), «Характеристики производных графов», Журнал комбинаторной теории , 9 (2): 129–135, doi : 10.1016/S0021-9800(70)80019-9 , MR  0262097.
• Цветкович, Драгош; Роулинсон, Питер; Симич, Слободан (2004), Спектральные обобщения линейных графов , Серия лекций Лондонского математического общества, том. 314, Кембридж: Издательство Кембриджского университета, номер документа : 10.1017/CBO9780511751752, ISBN. 0-521-83663-8, МР  2120511.
• Деджорджи, Даниэле Джорджио; Саймон, Клаус (1995), «Динамический алгоритм распознавания линейных графов», Теоретико-графовые концепции в информатике (Аахен, 1995) , Конспекты лекций по информатике, том. 1017, Берлин: Springer, стр. 37–48, номер документа : 10.1007/3-540-60618-1_64, MR  1400011..
• Эванс, Т.С.; Ламбьотт, Р. (2009), «Линейные графики, разделы ссылок и перекрывающиеся сообщества», Physical Review E , 80 (1): 016105, arXiv : 0903.2181 , Bibcode : 2009PhRvE..80a6105E, doi : 10.1103/PhysRevE.80.016105, PMID  19658772.
• Эванс, Т.С.; Ламбьотт, Р. (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.
• Гринвелл, Д.Л.; Хеммингер, Роберт Л. (1972), «Запрещенные подграфы для графов с плоскими линейными графиками», Discrete Mathematics , 2 : 31–34, doi : 10.1016/0012-365X(72)90058-1 , MR  0297604.
• Харари, Ф .; Норман, Р.З. (1960), «Некоторые свойства линейных орграфов», Rendiconti del Circolo Matematico di Palermo , 9 (2): 161–169, doi : 10.1007/BF02854581, hdl : 10338.dmlcz/128114 , S2CID  122473974.
• Харари, Ф. (1972), «8. Линейные графики», Теория графов (PDF) , Массачусетс: Аддисон-Уэсли, стр. 71–83, заархивировано из оригинала (PDF) 07 февраля 2017 г. , получено в 2013 г. 11-08.
• Хеммингер, РЛ; Бейнеке, Л.В. (1978), «Линейные графики и линейные орграфы», в Бейнеке, Л.В.; Уилсон, Р.Дж. (ред.), «Избранные темы теории графов» , Academic Press Inc., стр. 271–305..
• Юнг, Х.А. (1966), «Zu einem Isomorphiesatz von H. Whitney für Graphen», Mathematische Annalen (на немецком языке), 164 (3): 270–271, doi : 10.1007/BF01360250, MR  0197353, S2CID  119898359.
• Краус, Дж. (1943), "Новая демонстрация теории Уитни в сюр-ле-резо", Мат. Физ. Лапок , 50 : 75–85, МР  0018403.
• Лео, Филипп Г.Х. (1974), «Оптимальный алгоритм для обнаружения линейного графа и вывода его корневого графа», Journal of the ACM , 21 (4): 569–575, doi : 10.1145/321850.321853 , MR  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 Hungarica , 16 (3–4): 263–269, doi : 10.1007 /BF01904834 , hdl : 10338.dmlcz/140421 , S2CID  122866512.
• Руссопулос, Н. Д. (1973), «Алгоритм max { m , n } для определения графа H по его линейному графу G », Information Processing Letters , 2 (4): 108–112, doi : 10.1016/0020-0190 (73 )90029-X, МР  0424435.
• Рыячек, Зденек; Врана, Петр (2011), «Линейные графы мультиграфов и гамильтоновая связность графов без клешней», Journal of Graph Theory , 66 (2): 152–173, doi : 10.1002/jgt.20498, MR  2778727, S2CID  8880045.
• Седлачек, Дж. (1964), «Некоторые свойства графов обмена», Теория графов и ее приложения (Proc. Sympos. Smolenice, 1963) , Publ. Дом Чехословацкой академии. Sci., Прага, стр. 145–150, MR  0173255..
• Сысло, Мацей М. (1982), «Алгоритм разметки для распознавания линейного орграфа и вывода его корневого графа», Information Processing Letters , 15 (1): 28–30, doi : 10.1016/0020-0190(82)90080- 1, МР  0678028.
• Троттер, Л.Е. младший (1977), «Линейные совершенные графики», Mathematical Programming , 12 (2): 255–259, doi : 10.1007/BF01593791, MR  0457293, S2CID  38906333.
• де Верра, Д. (1978), «Совершенные онлайн-графы», Mathematical Programming , 15 (2): 236–238, doi : 10.1007/BF01609025, MR  0509968, S2CID  37062237.
• Уитни, Х. (1932), «Согласованные графы и связность графов», American Journal of Mathematics , 54 (1): 150–168, doi : 10.2307/2371086, hdl : 10338.dmlcz/101067 , JSTOR  2371086.
• Чжан, Фу Цзи; Линь, Го Нин (1987), «О графах де Брёйна – Гуда», Acta Math. Синица , 30 (2): 195–205, МР  0891925.
• Зверович, И. Э. (1997), Аналоговые выводы Уитни для реберных графов мультиграфов и реберных мультиграфов, Дискретная математика , 9 (2): 98–105, doi : 10.4213/dm478 , MR  1468075. В переводе на английский язык как Зверович, И.Э. (1997), «Аналог теоремы Уитни для реберных графов мультиграфов и реберных мультиграфов», Discrete Mathematics and Applications , 7 (3): 287–294, doi : 10.1515/dma.1997.7.3.287, S2CID  120525090.

Внешние ссылки

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