Изоморфизм графов

Изоморфные графы

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

Они могут отличаться графическим изображением и матрицами смежности и инцидентности. Чтобы убедиться, что два графа — это один и тот же граф, необходимо и достаточно установить взаимно однозначные соответствия между ними.

Необходимые условия, чтобы два графа были изоморфными:

1. Имеют одинаковое количество вершин и ребер

2. Вершины графов имеют одинаковые степени.

Но выполнение этих свойств не является достаточным условием для изоморфизма графов.

Пример: Построить граф изоморфный графу из предыдущего примера.

Путь и цикл в графе

Путем в графе называется последовательность ребер, ведущая от вершины к вершине .

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

Длинной цикла называется количество ребер в нем.

Если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

Связный граф является простым циклом тогда и только тогда, когда все его вершины имеют степень 2.

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

Ребро АВ называется мостом . если при его удалении вершины А и В остаются несвязными.

Здесь любое ребро является мостом

1. Ребро АВ является мостом, если АВ единственный путь, соединяющий вершину А с В.

2. АВ является мостом, когда ребро АВ не принадлежит ни одному циклу.

3. АВ. является мостом, если найдется две вершины С1 и С2 такие, что путь их соединяющий проходит через АВ.

188.123.231.15 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам.

Изоморфизм графов

Легко подсчитать число графов с фиксированным множеством вершин V. Эти графы различаются своими ребрами, и поэтому их число равно количеству подмножеств множества V´V, т.е. , где п = | V |. Однако эти графы на всегда следует различать. Как в применении теории графов, так и в самой этой теории чаще существенно лишь то, что есть объекты (вершины графа) и связи между объектами (ребра графа). С этих позиций графы, которые получаются один из другого изменением наименований вершин, разумно не различать. Такие графы называются изоморфными.

Пусть G и Н – графы, а – биекция. Если для любых вершин и и v графа G их образы и смежны в Н тогда и только тогда, когда и и v смежны в G, то эта биекция называется изоморфизмом графа G на граф Н. Если такой изоморфизм существует, то мы пишем и говорим, что графы G и Н изоморфны.

Пример 1. Графы, представленные на рис. 2.8 изоморфны, указана соответствующая изоморфизмам нумерация вершин. Графы на рис. 2.9 неизоморфны (например, вследствие того, что в первом графе есть циклы из трех ребер, а во втором их нет).

Очевидно, что отношение изоморфизма графов является эквивалентностью, т.е.

оно симметрично, рефлексивно и транзитивно. Следовательно, все графы разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы естественно отождествлять, т.е. считать совпадающими (их можно изобразить одним рисунком). Они могли бы различаться конкретной природой своих элементов, но именно это игнорируется при введении понятия графа. Класс изоморфных графов принято называть абстрактным графом.

В некоторых случаях приходится различать изоморфные графы. Граф порядка п называется помеченным, если его вершинам присвоены некоторые метки, например, номера 1, 2, …, п. Отождествив каждую из вершин графа с ее номером (а, следовательно, множество вершин – с множеством чисел <1, 2, …, п>), определим равенство графов G и Н одного и того же порядка: G = Н тогда, когда ЕG = ЕН. На рис. 2.10 изображены три разных помеченных графа.

Число gn помеченных графов порядка п определяется сложно. Известна формула Пойа

дающая асимптотику числа gn. Эта формула означает, что две функции g(п)=gn и f(n)= асимптотически равны, т.е. .

Реферат на тему:

Изоморфизм графов

    Введение
  • 1 Пример
  • 2 Изоморфизм графов общего вида
    • 2.1 Теорема Уитни
    • 2.2 Инварианты
    • 2.3 Модульное произведение Визинга
  • 3 Изоморфизм графов специального вида
  • 4 Вычислительная сложность
  • 5 Применения Примечания

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

Иногда биекция f записывается в виде подстановки изоморфизма . Некоторые задачи обработки графов требуют не только проверки изоморфизма, но и выяснения его подстановки.

Отношение изоморфизма графов представляет собой отношение эквивалентности, определенное для графов, и позволяет произвести разбиение исходного класса всех графов на классы эквивалентности. Множество графов, изоморфных друг другу, называется классом изоморфизма графов (англ. ), их число в зависимости от n представляет собой последовательность A000088 в OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346. ).

В случае, если биекция f отображает граф сам на себя (графы G и H совпадают), она называется автоморфизмом графа G .

Два графа, приведенные в примере, являются изоморфными.

Изоморфизм между графами G и H

Подстановка изоморфизма f

2. Изоморфизм графов общего вида

Графы G и H являются изоморфными, если путем перестановки строк и столбцов матрицы смежности графа G удается получить матрицу смежности графа H. Однако перебор всех возможных перестановок характеризуется вычислительной сложностью O (N !) (при условии, что сравнение матриц смежности производится за время, не зависящее от N. что обычно несправедливо и дополнительно увеличивает приведенную оценку), что существенно ограничивает применение подобного подхода на практике. Существуют методы ограниченного перебора возможных пар предположительно-изоморфных вершин (аналог метода ветвей и границ), однако они незначительно улучшают приведенную выше асимптотику [1] .

2.1. Теорема Уитни

Исключение из теоремы Уитни: представленные графы K3 (слева) и K1,3 (справа) не изоморфны, однако их линейные графы изоморфны

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

2.2. Инварианты

Существует набор числовых характеристик графов, называемых инвариантами. которые совпадают у изоморфных графов (совпадение инвариантов является необходимым, но не достаточным условием наличия изоморфизма) [4]. К ним относятся число вершин n (G ) и число дуг/ребер m (G ) графа G. упорядоченный по возрастанию или убыванию вектор степеней вершин , упорядоченный по возрастанию или убыванию вектор собственных чисел матрицы смежности графа (спектр графа), хроматическое число χ(G ) и др. Факт совпадения инвариантов обычно не несет информации о подстановке изоморфизма.

Инвариант называется полным. если совпадения инвариантов графов необходимо и достаточно для установления изоморфизма. Например, каждое из значений μmin (G ) и μmax (G ) (мини- и макси-код матрицы смежности) является полным инвариантом для графа с фиксированным числом вершин n .

Различные инварианты имеют различную трудоемкость вычисления. В настоящее время полный инвариант графа, вычислимый за полиномиальное время, неизвестен, однако не доказано, что он не существует. Попытки его отыскания неоднократно предпринимались в 60-х — 80-х годах XX века, однако не увенчались успехом.

2.3. Модульное произведение Визинга

Модульное произведение графов , предложенное В. Г. Визингом (англ. ), позволяет свести задачу проверки изоморфизма к задаче определения плотности графа , содержащего вершин. Если , , то граф H содержит подграф, изоморфный графу G .

3. Изоморфизм графов специального вида

4. Вычислительная сложность

Хотя задача распознавания изоморфизма графов принадлежит классу NP, неизвестно является ли она NP-полной или принадлежит классу P (при условии, что P ≠ NP). При этом задача поиска изоморфного подграфа (англ. ) в графе является NP-полной. Современные исследования направлены на разработку быстрых алгоритмов решения как общей задачи изоморфизма произвольных графов, так и графов специального вида.

5. Применения

На практике необходимость проверки изоморфизма графов возникает при решении задач хемоинформатики, математической (компьютерной) химии [5]. автоматизации проектирования электронных схем (верификация различных представлений электронной схемы) [1]. оптимизации программ (выделение общих подвыражений).

Примечания

  1. 12Курейчик В. М. Глушань В. М. Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. — М. Радио и связь, 1990. — 216 с.
  2. H. Whitney (1932). «Congruent graphs and the connectivity of graphs». Am. J. Math.54. 160-168. DOI:10.2307/2371086 — dx.doi.org/10.2307/2371086.
  3. Dirk L. Vertigan, Geoffrey P. Whittle (1997). «A 2-Isomorphism Theorem for Hypergraphs — homepages.mcs.vuw.ac.nz/

whittle/pubs/2-isomorphism_theorem_for_hypergraphs.pdf». J. Comb. Theory, Ser. B71 (2): 215-230. DOI:10.1006/jctb.1997.1789 — dx.doi.org/10.1006/jctb.1997.1789.

  • Зыков А. А.  Основы теории графов. — М. Наука, 1986. — 384 с. — ISBN 978-5-9502-0057-1
  • Трофимов М. И. Смоленский Е. А.  Применение индексов электроотрицательности органических молекул в задачах химической информатики // Известия Академии наук. Серия химическая. — 2005. — С. 2166—2176.
  • Изоморфизм графов

    В теории графов изоморфизмом графов G = ⟨ V G. E G ⟩ <\displaystyle G=\left\langle V_,E_\right\rangle > и H = ⟨ V H. E H ⟩ <\displaystyle H=\left\langle V_,E_\right\rangle > называется биекция между множествами вершин графов f. V G → V H <\displaystyle f\colon \ V_\rightarrow V_> такая, что любые две вершины u <\displaystyle u> и v <\displaystyle v> графа G <\displaystyle G> смежны тогда и только тогда, когда вершины f ( u ) <\displaystyle f(u)> и f ( v ) <\displaystyle f(v)> смежны в графе H <\displaystyle H> . Здесь графы понимаются неориентированными и не имеющими весов вершин и ребер. В случае, если понятие изоморфизма применяется к ориентированным или взвешенным графам, накладываются дополнительные ограничения на сохранение ориентации дуг и значений весов. Если изоморфизм графов установлен, они называются изоморфными и обозначаются как G ≃ H <\displaystyle G\simeq H> .

    Иногда биекция f <\displaystyle f> записывается в виде подстановки изоморфизма ( a 1 a 2 … a n f ( a 1 ) f ( a 2 ) … f ( a n ) ) <\displaystyle <\begina_<1>&a_<2>9amp;\dots &a_\\f(a_<1>)9amp;f(a_<2>)9amp;\dots &f(a_)\end>> . Некоторые задачи обработки графов требуют не только проверки изоморфизма, но и выяснения его подстановки.

    Отношение изоморфизма графов представляет собой отношение эквивалентности. определенное для графов, и позволяет произвести разбиение исходного класса всех графов на классы эквивалентности. Множество графов, изоморфных друг другу, называется классом изоморфизма графов (англ. ). их число в зависимости от n <\displaystyle n> представляет собой последовательность A000088 в OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346. ).

    Существуют также смежные задачи теории графов, такие как поиск изоморфного подграфа и поиск максимального общего изоморфного подграфа (англ. ). принадлежащие к классу NP-полных. В смежных разделах математики существуют схожие проблемы, например изоморфизма проективных плоскостей и изоморфизма конечных групп. которые полиномиально сводятся к проблеме изоморфизма графов (возможность обратной полиномиальной сводимости в общем случае не доказана) [1] .

    Содержание

    Два графа, приведенные в примере, являются изоморфными.

    Подстановка изоморфизма f <\displaystyle f>

    ( a b c d g h i j 1 6 8 3 5 2 4 7 ) <\displaystyle <\begina&b9amp;c9amp;d9amp;g9amp;h9amp;i9amp;j\\19amp;69amp;89amp;39amp;59amp;29amp;49amp;7\end>>

    Изоморфизм графов общего вида

    Графы G <\displaystyle G> и H <\displaystyle H> являются изоморфными, если путём перестановки строк и столбцов матрицы смежности графа G <\displaystyle G> удается получить матрицу смежности графа H <\displaystyle H> . Однако перебор всех возможных перестановок характеризуется вычислительной сложностью O ( N. ) <\displaystyle O(N!)> (при условии, что сравнение матриц смежности производится за время, не зависящее от N <\displaystyle N> . что обычно несправедливо и дополнительно увеличивает приведенную оценку), что существенно ограничивает применение подобного подхода на практике. Существуют методы ограниченного перебора возможных пар предположительно-изоморфных вершин (аналог метода ветвей и границ ), однако они незначительно улучшают приведенную выше асимптотику [2] .

    Теорема Уитни

    Исключение из теоремы Уитни: представленные графы K 3 <\displaystyle K_<3>> (слева) и K 1. 3 <\displaystyle K_<1,3>> (справа) не изоморфны, однако их рёберные графы изоморфны

    Теорема Уитни об изоморфизме графов [3] [4]. сформулированная Хасслером Уитни в 1932 году. гласит, что два связных графа изоморфны, тогда и только тогда, когда их рёберные графы изоморфны, за исключением графов K 3 <\displaystyle K_<3>> (полного графа из 3 вершин) и полного двудольного графа K 1. 3 <\displaystyle K_<1,3>> . которые не являются изоморфными, однако оба имеют граф K 3 <\displaystyle K_<3>> в качестве рёберного графа. Теорема Уитни может быть обобщена для гиперграфов [5] .

    Инварианты

    Существует набор числовых характеристик графов, называемых инвариантами. которые совпадают у изоморфных графов (совпадение инвариантов является необходимым. но не достаточным условием наличия изоморфизма) [6]. К ним относятся число вершин n ( G ) <\displaystyle n(G)> и число дуг/ребер m ( G ) <\displaystyle m(G)> графа G. упорядоченный по возрастанию или убыванию вектор степеней вершин s ( G ) = ( ρ ( v 1 ). ρ ( v 2 ). …. ρ ( v n ) ) <\displaystyle s(G)=(\rho (v_<1>),\rho (v_<2>),\dots ,\rho (v_))> . упорядоченный по возрастанию или убыванию вектор собственных чисел матрицы смежности графа (спектр графа), хроматическое число χ ( G ) <\displaystyle \chi (G)> и др. Факт совпадения инвариантов обычно не несет информации о подстановке изоморфизма.

    Инвариант называется полным. если совпадения инвариантов графов необходимо и достаточно для установления изоморфизма. Например, каждое из значений μ m i n ( G ) <\displaystyle \mu _(G)> и μ m a x ( G ) <\displaystyle \mu _(G)> (мини- и макси-код матрицы смежности) является полным инвариантом для графа с фиксированным числом вершин n <\displaystyle n> .

    Различные инварианты имеют различную трудоемкость вычисления. В настоящее время полный инвариант графа, вычислимый за полиномиальное время, неизвестен, однако не доказано, что он не существует. Попытки его отыскания неоднократно предпринимались в 60-х — 80-х годах XX века. однако не увенчались успехом.

    Модульное произведение Визинга

    Модульное произведение графов Y = G ◊ H <\displaystyle Y=G\lozenge H> . предложенное В. Г. Визингом. позволяет свести задачу проверки изоморфизма к задаче определения плотности графа φ ( Y ) <\displaystyle \varphi (Y)> . содержащего n ( G ) ⋅ n ( H ) <\displaystyle n(G)\cdot n(H)> вершин. Если φ ( Y ) = n ( G ) <\displaystyle \varphi (Y)=n(G)> . n ( G ) ≤ n ( H ) <\displaystyle n(G)\leq n(H)> . то граф H <\displaystyle H> содержит подграф, изоморфный графу G <\displaystyle G> .

    Изоморфизм графов специального вида

    ГРАФОВ ИЗОМОРФИЗМ это:

    — отношение эквивалентности на множестве графов. Изоморфным отображением одного неориентированного графа на другой наз. взаимно однозначное отображение вершин и ребер одного графа соответственно на вершиныи ребра другого графа, при к-ром сохраняется отношение инцидентности. Два графа наз. изоморфными, если существует изоморфное отображение одного из этих графов на другой. Графы G1 и G2. представленные на рис. не изоморфны, a G1 и G3 изоморфны. Обычно изоморфные графы не различают. Число попарно неизоморфных графов с данным числом вершин и данным числом ребер конечно. Подобным образом можно определить изоморфизм ориентированных графов, гиперграфов и сетей.

    Изоморфизм графов

    Изоморфизм графов

    Изоморфизм графов

    Проблема установления Г. и. является важной проблемой теории графов. Для нек-рых классов графов имеются алгоритмы, позволяющие установить изоморфизм достаточно эффективно (напр. для деревьев или плоских графов, см. [1]). Для нек-рых классов графов с пвершинами доказана однозначная (с точностью до изоморфизма) восстанавливаемость графа по набору всех его Изоморфизм графов -вершин ных подграфов Изоморфизм графов. получаемых удалением всевозможных вершин Изоморфизм графов. Это установлено, в частности, для деревьев и турниров (при Изоморфизм графов ).

    Лит. :[1] Хопкрофт Дж. Тарьян Р. «Кибернетический сборник», 1975, в. 12, с. 3&-61; [2] Kelly P. J. «Pacific J. Math.», 1957, v. 7, p. 961-68. В. Б. Алексеев.

    Математическая энциклопедия. — М. Советская энциклопедия. И. М. Виноградов. 1977—1985 .

    Смотреть что такое «ГРАФОВ ИЗОМОРФИЗМ» в других словарях:

    ГРАФОВ ГОМЕОМОРФИЗМ — отношение эквивалентности на множестве графов, характеризующее их геометрия, свойства. Г. г. определяется следуюпшм образом. Подразбиением ребра ( а, b).графа Gназ. операция, состоящая в добавлении новой вершины v, удалении ребра (а, b).и… … Математическая энциклопедия

    Изоморфизм графов — В теории графов изоморфизмом графов и называется биекция между множествами вершин графов такая, что любые две вершины и графа смежны, тогда и только тогда, когда вершины … Википедия

    Изоморфизм — У этого термина существуют и другие значения, см. Изоморфизм (значения). Изоморфизм (от др. греч. ἴσος «равный, одинаковый, подобный» и μορφή «форма»)  это очень общее понятие, которое употребляется в различных разделах математики. В общих… … Википедия

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

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

    Теория графов и мографов — Теорема 3.27. замена любого ребра (a, b)in Gкритического графа G на k вершинно непересекающихся простых цепей длинны 3 тогда и только тогда приводят к образованию критического графа T 3(G), когда k удовлетворяет одному из следующих условий: # k=1 … Википедия

    Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия

    Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия

    Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

    Цикл (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

    • Изоморфизм графов. Джесси Рассел. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. High Quality Content by WIKIPEDIA articles! В теории графов изоморфизмом графов и называется… Подробнее Купить за 998 руб
    • Графы и их применение. Комбинаторные алгоритмы для программистов. Н. И. Костюкова. Содержание учебника разделяется на две части. Первая часть посвящена изучению теории графов. Она включает в себя такие темы, как связность, деревья, эйлеровы и гамильтоновы цепи и циклы,… Подробнее Купить за 295 руб

    Добавить комментарий

    Ваш e-mail не будет опубликован. Обязательные поля помечены *