Графы изоморфные

Граф G=(X, U) называют плоским, если его множество ребер расположено на плоскости таким образом, что ребра имеют общие точки лишь в вершинах. Граф, изоморфный плоскому и расположенный на плоскости с пересечением ребер, называют планарным. [c.211]

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

Два графа G=(X, U) и G =(X, U ) называют изоморфными, если можно установить взаимно однозначное соответствие Х- -X, U U такое, что если (Xi, [c.211]

Изоморфные графы могут быть получены один из другого путем перенумерации их вершин. Очевидно, что изоморфизм есть отношение эквивалентности на графах. Если изоморфные преобразования проводятся с графом, заданным матрицей смежности, то они сводятся к перестановке местами соответствующих строк и столбцов. Известно, что в общем случае для определения изоморфизма графов необходимо сделать п сравнений или перестановок строк и столбцов матрицы, что для графов с л>30 не под силу даже современной ЭВМ. Поэтому необходимо применить тот или иной эвристический алгоритм поиска по дереву решений. [c.211]

Пусть задан граф G=(X, U). Подразбиением ребра Uk= Xi, Xj) называют замену его двумя ребрами щу — == Xi, х ) и Up2=(Xp, Xj) с введением новой вершины Хр. Два графа называют гомеоморфными, если они обладают изоморфными подразбиениями. [c.212]

Граф, вершинам которого приписываются целые числа от 1 до Я, называется помеченным (рис. 34, с). Два помеченных графа Gj и Gj называются изоморфными, если существует взаимно однозначное отображение множества X (Gj) на множество X (Ог), сохраняющее не только смежность, но и распределение пометок. Примером изоморфных графов может служить СС и соответствующий ей ГЧВ (см. рис. 29 и 30). Сразу же оговоримся, что пометки вершин в СС и ГЧВ отличаются от принятых в теории графов подробнее об этом будет сказано ниже. [c.76]

Всю информацию о структуре конструкций необходимо формализовать в виде упорядоченных множеств цифр, изоморфных реальным элементам конструкций и связям между ними. Наиболее удобным математическим аппаратом для этой цели является теория графов [48]. [c.68]

Графы, у которых существуют одинаковые (совпадающие) представления, называются изоморфными. Точнее, графы Г = и Г = (Z, U y [c.13]

Например, графы, изображенные на рис. 1.3,6, в, изоморфные, так как существует отображение [c.14]

По существу изоморфные графы отличаются лишь нумерацией вершин. Так, например, списки ребер графов, изображенных на рис. 2.2, имеют вид ], 2) 1,3)(1,4) 2,3) 3,4)-(рж. 2.2, а) [1, 3) (1,4) (2,3) [c.38]

Нитрид бора (ВN) изоморфен графиту, но не обеспечивает, как это можно было бы ожидать, смазку при действии больших нагрузок. Как и графит, под действием высоких давлений BN может принять кубическую модификацию, изоморфную алмазу. Благодаря гексагональной графитовой структуре BN в обычном состоянии весьма анизотропен и после горячего прессования получает текстуру и анизотропию свойств, как и графит. [c.51]

Два графа G = (V, E) и G = V, E ) изоморфны друг другу, если существует взаимно однозначное соответствие между V п V и между Е и Е, сохраняющее инцидентность. Например, два графа, показанные на рис. П.5, изоморфны. [c.284]

Простой граф G = (l/, Е), у которого У = п и любая пара вершин соединена ребром, называется полным графом для п-вершин. Легко убедиться, что полный граф имеет п(п — 1)/2 ребер. Так как любые два полных графа, имеющие одинаковое число вершин, изоморфны, говорят о полном графе для п-вершин. [c.284]

Подсчитайте число суграфов, включая изоморфные, в графе G=(X, U), X =rt. [c.221]

Граф с корнем (или корневой граф) имеет одну выделенную вершину, называемую корнем [ 131 ]. На рис. 34, б показан корневой граф с корнем в вершине Xj. Понятие изоморфности для корневых графов Gj и Gj предусматривает сохранение во взаимно однозначном отображении множества X (G,) на множества X (Gj) наряду со смежностью и распределением пометок также и корни. [c.76]

Применяя последовательно преобразование Q к исходному графу Gq, можно получить множество Ga всех шестивершинных и множество Gs всех пятивершинных производных графов. Далее, сравнивая каждый граф из Ge и из Gs соответственно с типовыми Кг,ъ и Кз, на основании теоремы 5.1 можно сделать заключение о планарности графа Gq. Другими словами, если среди Ge найдется граф Ge, изоморфный 3,3, или среди G5 —граф G5, изоморфный Кь, то исходный граф Gq следует признать неиланарным. В противном случае, Gq планарен. [c.179]

Теперь пусть s = 3. В этом случае согласно Л в G должны быть удалены и ребра цикла, образующего грань, поэтому пересечение в области D можно попытаться устранить путем изменения порядка следования ребер (осьР), ( 2, Р), ( 3, Р), получаемого при обходе вершины р против часовой стрелки. Однако нетрудно убедиться, что получаемые при этом топологические графы будут изоморфны друг другу. Значит, и в этом случае остается принять, что граф AG планарный. Теорема доказана. [c.193]

Геометрия камеры группы полностью определяется графом Кокстера, вершины которого соответствуют стенкам камеры. Две вершины соединены ребром кратности к, если угол между соответствующими стенками равен я/ . Группы с одинаковыми графами Кокстера изоморфны. [c.127]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...