Пример - граф
Cтраница 4
Нами показано, что некоторые реакционные графы, встречающиеся в химической литературе, являются примерами графов, известных специалистам по теории групп как суборбитальные графы. В настоящей статье мы ограничились рассмотрением особых типов реакционных графов - графов, в которых перегруппировки исходного графа приводят к изоморфному графу ( вырожденные перегруппировки), и нами всегда допускалось, что на исходный граф действует группа полной симметрии. Основываясь на общих свойствах суборбитальных графов, мы пришли к выводу, что группа автоморфизмов такого реакционного графа всегда содержит симметрическую группу Sn, и рассмотрели условия, при которых реакционный граф является связным. [46]
 |
Два 4-хроматических пленарных графа. [47] |
Если будет доказана гипотеза четырех красок, то результат будет неулучшаем, поскольку легко привести примеры планарных 4-хроматических графов. Таковы графы / С4 и We, изображенные на рис. 12.3. В каждом из этих графов не менее четырех треугольников, что является в силу теоремы Грюнбаума [1] необходимым условием 4-хроматичности. [48]
Дерево графа и матрицу главных сечений можно получить на основе структурной матрицы АО по формальному алгоритму, который поясним на примере графа рис. 1.29 я. Выбираем в первом столбце матрицы А ( 1 первый ненулевой элемент и соответствующую этому элементу строку прибавим или вычтем из строк, соответствующих ненулевым элементам этого же столбца так, чтобы образовался столбец с единственным ненулевым элементом. Если этот элемент равен - 1, меняем знаки в соответствующей ему строке на обратные и переставляем эту строку на первое место. [49]
Аналогично если множество записи класса К пересекается с множеством чтения класса /, то в графе присутствует ребро ( /, wh), которое называется диагональным, На рис. 6.11 приведен пример графа конфликтов для классов транзакций, соответствующих транзакциям из предыдущего примера. [50]
 |
Граф переходов машины Тьюринга. [51] |
Так, известные графы переходов есть не что иное как графическое изображение системы продукций. Пример графа переходов для машины Тьюринга из упражнения 2.3 приведен на рис. 3.2. На этом рисунке вершины соответствуют состояниям машины Тьюринга, а связи - командам-продукциям. Над связью указан читаемый символ, под связью - исполняемое действие. [52]
Очевидно, что если любой граф содержит такой пятивершинный граф ( или, вообще, любой неплоский граф) в качестве подграфа, то он обязательно неплоский. Примером неплоского графа, который не содержит упомянутого полного графа, является граф в задаче о трех пунктах обслуживания и трех домах), приведенный на рис. 4.3. Будем называть такой граф графом Понтрягина - Куратовского 1-го типа. Граф ы Понтрягина - Куратовского 1-го и 2-го типов позволяют определить наиболее общее условие существования плоского графа. [53]
В настоящем разделе дается формальное определение графа и вводится основополагающая терминология теории графов. Приводятся примеры графов и некоторые простые теоремы. [54]
Страницы: 1 2 3 4