Два - граф
Cтраница 1
 |
Запрещенные графы для внешней планарности. [1] |
Два графа называются гомеоморфными, если их можно получить из одного графа с помощью последовательности подразбиений ребер. [2]
Два графа, вершины которых помечены, считаются тождественными ( неразличимыми) в том и только в том случае, когда любые две вершины, помеченные одинаково в обоих графах, имеют одинаковое число инцидентных им ребер. Так, два графа могут считаться различными, даже еслч они изоморфны. [3]
 |
Графы с четырьмя вершинами. [4] |
Два графа изоморфны, если существует взаимно однозначное соответствие между множествами их вершин, сохраняющее отношение смежности. На рис. 1 показаны все графы ( с точностью до изоморфизма), состоящие из четырех вершин. [5]
 |
Два непланарных графа. [6] |
Два графа называются гомеоморфными, если они обладают изоморфными подразбиениями. Куратовский показал, что граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных графам / Сз. [7]
Два графа, Gi ( Jb FI) и G2 ( X2, F2), называются изоморфными ( G. Заметим, что взаимно-однозначное отображение / может иметь место только для эквивалентных вершин с одинаковыми метками. [8]
Два графа гомеоморфны, если оба они могут быть получены из одного и того же графа последовательностью подразбиений линий; например, два цикла геомеоморфны. [9]
Два графа G4 и G2 называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые две вершины в Glf равно числу ребер, соединяющих соответствующие вершины в Gz. Так, два графа, изображенные на рис. 2.5, изоморфны при соответствии и I, v т, w п, х р, у q, z - г. Заметим, что эти графы имеют по шесть вершин - другие точки пересечения ребер вершинами не являются. [10]
Два графа можно соединить каскадно, если только они совместимы. [11]
Два графа мы будем считать эквивалентными, если между их вершинами можно установить соответствие так, чтобы входы и выходы соответствовали друг другу и число ребер, соединяющих соответствующие пары вершин, в обоих графах было бы одинаково. Мы для удобства рассматриваем лишь графы с выделенными вершинами: входом и выходом. [12]
Два графа называются гомеоморфными, если их можно получить из одного графа с помощью последовательности подразбиений ребер. [13]
 |
Помеченные и непомеченный графы.| Граф и два его подграфа. [14] |
Два графа G и Я изоморфны ( записывается G H или иногда 0 - Я), если между их множествами вершин существует взаимно однозначное соответствие, сохраняющее смежность. Например, d и GI на рис. 2.5 изоморфны при соответствии v ut и чисто случайно оказалось, что граф G3 изоморфен каждому из них. Совершенно очевидно, что изоморфизм есть отношение эквивалентности на графах. [15]
Страницы: 1 2 3 4