Конструктивное описание графов

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

КОНСТРУКТИВНЫЕ  ОПИСАНИЯ ГРАФОВ

Курсовая работа студента                                                                            дневного отделения 3-го                                                              курса 334 группы                                                                                            Ухов Ю.В.

Научный руководитель:                                                                                                       Профессор. Доктор физико-                                                               математических наук                                                        Иорданский М. А.

Нижний Новгород 2008г.

Оглавление

Стр.

Введение…………………………………………………………………………………………………………3

Глава 1. Конструктивное описание графов: елементный  и операционный базисы, структура и способы порождения замкнутых классов графов

       § 1. Определения основных понятий и обозначения……………………4

 

       § 2. Свойства операций склейки……….…………………………………6

 

       § 3. Структура замкнутых и if-замкнутых классов графов.…………….8

 

       § 4. Базисы классов всех графов, мультиграфов и обыкновенных графов…………………………………………………………………………...9

Глава 2. Условия наследования графов

       §1. Условия наследования триангулированности графов......................11

 

       §2. Условия наследования планарности графов…………………..…...12

 

       § 3. Условие наследования планарности максимальных графов………………………………………………………………………....15

Заключение……………………………………………………………………

 

ЛИТЕРАТУРА…………………………………………………………….….27

 

 

 

 

 

 

 

 

 

 

Введение.

Рассматриваются процессы построения графов с помощью  операций объединения с пересечением (операции склейки). Изучается структура замкнутых классов системы (Q,C), где Q-множество всех графов, С — суперпозиция операций склейки. Установлено, что каждый замкнутый класс графов имеет единственный базис; существуют классы со счетными базисами; мощность множества всех замкнутых классов графов континуальна. Таким образом, система (Q, С) занимает промежуточное положение по структуре замкнутых классов между системами ( ,С) и ( ,C), где — множество всех функций алгебры логики, Рk — множество всех функций k-значной логики, к ≥ 3. Выделены конечные базисы классов всех графов, мультиграфов и простых графов. Найдены необходимые и достаточные условия наследования при выполнении операций склейки таких свойств графов, как триангулированность, планарность и максимальная планарность. Получены элементные и операционные базисы соответствующих классов планарных графов.

Широкое использование  теоретико-графовых моделей в задачах дискретной математики требует разработки методов анализа структур графов, в частности графов, обладающих тем или иным характеристическим

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

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

как это делается при изучении строения и функционирования управляющих

систем . Каждый граф строится из исходных, базисных графов с помощью бинарной операции склейки, являющейся обобщением теоретико- ножественных операций объединения и пересечения. «Сила» операций регулируется ограничениями, обеспечивающими наследование требуемых свойств графов. Ограничения в виде необходимых и достаточных условий задают динамическую структурную характеризацию соответствующих замкнутых классов графов.

В § 1 приводятся определения основных понятий, используемых при конструктивном описании графов. В § 2 рассматриваются свойства операции

склейки графов. В § 3 изучается структура замкнутых  классов системы (Q,С), где Q-множество всех графов, С — операция суперпозиции.

В § 4 определяются базисы замкнутых классов всех графов, мультиграфов и обыкновенных графов. В § 5 — 7 дается динамическая структурная характеризация соответственно классов хордальных, планарных и максимальных планарных графов. В § 8 приводятся конечные описания класса планарных графов. В § 9 получены конечные базисы ряда классов хордальных планарных графов.

§ 1. Определения основных понятий и обозначения

Объектом исследований являются конечные псевдографы, мульти- графы и обыкновенные графы.

Псевдограф  — это пара (V, E), где V — непустое множество (вершин), a E— некоторая совокупность (вообще говоря, с повторениями) неупорядоченных пар вершин (ребер). (При обращении к псевдографам для краткости используется термин «граф».)

Мультиграф  — это псевдограф без петель.

Обыкновенный  граф — это мультиграф без кратных  ребер.

Если G — граф, то V(G) и E(G), как обычно, обозначают соответственно

множество вершин и множество ребер в G.

Все графы рассматриваются с точностью до изоморфизма. Граф G' называется частью графа G, если V(G') V(G) и E(G')     E(G) (обозначается как G'     G). Часть G' графа G называется подграфом графа G, если E(G') содержит все ребра графа G, соединяющие вершины из V(G').

Пусть и — непересекающиеся графы, т. е. V( )∩ V( ) =Ø, содержащие изоморфные части G1'     G1и G2'     G2.

ОПРЕДЕЛЕНИЕ 1. Объединение графов и путем отождествления их изоморфных частей '     и '     называется операцией склейки графов и .

Граф G, получаемый при выполнении операции склейки, называется результирующим графом (склейкой графов), графы G1 и G2 — графами-операндами. Поскольку графы-операнды изоморфны частям результирующего графа, то для числа вершин и ребер графов , и G справедливы соотношения \V( )\ + \V( )\ ≥ \V(G)\ ≥ max{\V( )\, \V( )\},

\E( )\ + \E( )\ ≥ \E(G)\ ≥ max { \E( )\ , \E( )\}.

При одновременном достижении левых равенств операция склейки графов G1и G2 совпадает с операцией их объединения без пересечения. При одновременном достижении правых равенств операция склейки называется тривиальной. В этом случае ' = или (и) ' = и происходит изоморфное вложение одного графа-операнда в другой. Операции склейки фиксированных графов-операндов не различаются, если их результирующие графы изоморфны. Различные операции относятся к одному типу, если их отождествляемые части изоморфны фиксированному графу.

Пусть Р и Н — некоторые (не обязательно конечные) множества графов и типов операций склейки. Операции из Н называются операциями Н- склейки.

ОПРЕДЕЛЕНИЕ 2. Граф G называется Н-суперпозицией графов из Р, если G ϵ Р или G можно получить из графов множества Р путем последовательного применения операций H-склейки. Процесс построения графа G называется операцией Н-суперпозиции графов из Р.

ОПРЕДЕЛЕНИЕ 3. Множество  всех графов, получаемых из Р с помощью

операций H-суперпозиции, называется Н-замыканием множества Р и бозначается через [Р]h. Если [P]h = Р, то Р называется Н- замкнутым классом графов.

ОПРЕДЕЛЕНИЕ 4. Минимальная  по включению система графов Вэ     Р называется элементным базисом H-замкнутого класса Р, если [Вэ]h= Р.

ОПРЕДЕЛЕНИЕ 5. Система операций В0      H, содержащая минимальное

число типов операций, называется операционным базисом Н-замкнутого класса Р, если [Вэ] =Р.

ОПРЕДЕЛЕНИЕ 6. Операция склейки сохраняет заданное свойство графов-операндов, если этим свойством обладает результирующий граф. Если Р — множество всех графов, обладающих заданным свойством, то оно, очевидно, H-замкнуто относительно любого множества Н операций склейки, сохраняющих заданное свойство графов. H-замкнутый класс имеет конечное описание, если его элементный и операционный базисы содержат соответственно конечное число графов и типов операций. Рассматриваются конечные описания H-замкнутых классов графов. При этом в множества допустимых операций включаются как все операции, охраняющие заданное свойство графов, так и некоторые их подмножества.

Используются следующие  обозначения:

G(V') — подграф графа G с множеством вершин V'      V(G);

G(E') — часть графа G с семейством (множеством) ребер Е'    E(G) и множеством вершин, инцидентных ребрам из Е';

Кп — полный обыкновенный n-вершинный граф ( — граф, не содержащий вершин);

Ḡ — дополнение обыкновенного графа G до полного;

 — простой цикл длины п ≥1 ( — петля);

 — простая цепь длины п ≥ 2. _

В обозначениях однотипных операций указывается граф Ğ, изоморфный

отождествляемым частям графов-операндов. По отношению к любой такой операции используется терминология «операция склейки по Ğ», а ее результирующий граф обозначается через ( о )Ğ. Операции склейки по Ğ применимы к графам, содержащим части, изоморфные Ğ. Для упрощения записей обозначения графов и их изоморфных образов, получаемых при выполнении операций склейки, как правило, не различаются. Отождествленная часть результирующего графа операции склейки по Ğ также обозначается через Ğ.

При наличии симметрии  в графах-операндах и в их отождествляемых

частях операции одного типа могут иметь изоморфные графы (G1 оG2)Ğ  при любом выборе отождествляемых частей и их изоморфизмов. В таких случаях записи (G1 о G2)Ğ и их суперпозиции используются в качестве языка задания графов.

ПРИМЕР 1.

( о ) — объединение графов и без пересечения (склейка по );

( о ) — склейка графов и по \

(( о ) о ) — склейка графов ( о ) и по .

В обозначении  множества H допустимых операций указываются общие для всех операций H-склейки ограничения на выбор отождествляемых частей и способ их отождествления. Эти ограничения приводятся и в обозначениях однотипных операций H-склейки.

ПРИМЕР 2.

< Ğ > операции склейки по Ğ, в которых отождествляемые части графов-операндов выбираются таким образом, что несмежным в Ğ вершинам соответствуют несмежные вершины хотя бы в одном из графов- операндов; < H > множество всех операций < Ğ> различных типов.

Формула ( о ) реализует два неизоморфных графа (рис. 1).

 

 

При использовании операции < > в качестве однозначного результата имеем только граф ( о )К2.

< Ğ > — операции склейки по Ğ, в которых отождествляемые части графов-операндов являются подграфами; < Н > — множество всех операций < G > различных типов. Операция < > не применима к графу К3.

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

результирующих графов, обеспечивают наличие у всех получаемых графов заданного свойства.

ЗАМЕЧАНИЕ 1. Если Н содержит операции всех типов, применимых к графам из Р, и на выбор отождествляемых частей и способ отождествления

не накладываются никакие ограничения, то H-замкнутый класс Р называется также замкнутым. Если в описании замкнутого класса графов операционный базис не указывается, то термин «элементный базис» заменяется для краткости на «базис». Базис обозначается через В.

Определения всех используемых понятий можно найти в [1, 6, 7].

§ 2. Свойства операций склейки

Рассматривается связь некоторых общих структурных  характеристик графов-операндов и результирующих графов операций склейки. Формулируется ряд вспомогательных утверждений, используемых при конструктивном описании графов.

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

Свойство 2. Операция склейки сохраняет связность графов тогда

и только тогда, когда  Ğ ≠ .

Свойство 3. Операция склейки сохраняет отсутствие кратных ребер, если каждой паре несмежных в Ğ вершин соответствует пара несмежных вершин хотя бы в одном из графов и G2.

Подмножество V '    V(G) называется разделяющим множеством вершин графа G, если граф G(V\V') имеет больше компонент связности, чем граф G.

Свойство 4. Если \V(G)\ > max{|V( )|, |V( )|}, TO V(Ğ) является разделяющим множеством вершин связного графа G = ( о )Ğ. Указанное неравенство имеет место при выполнении любой нетривиальной

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

Лемма 1. ЕСЛИ V(Ğ) — тупиковое разделяющее множество вершин связного графа G = ( о )Ğ, то каждая вершина из V( )\V( ') и V( )\V( ') соединена с каждой вершиной из V(Ğ) цепью, не содержащей внутренних вершин из V(Ğ).

ДОКАЗАТЕЛЬСТВО. Предположим, что найдется такая вершина vi1 € V( )\V( ') (vi2 € V( )\V( ')), которая соединена с некоторой вершиной vio € V(Ğ) лишь цепями, содержащими внутренние вершины из V(Ğ). При этом множество V(Ğ)\{vi0} также будет разделяющим в графе G: одна компонента связности включает вершину vi1(vi2), а другая — вершину vi0, что противоречит условию тупиковости (минимальности по включению) разделяющего множества V(Ğ). Лемма 1 доказана.