для выполнения расчетно-графической работы




МЕТОДИЧЕСКИЕ УКАЗАНИЯ

по дисциплине "Дискретная математика и теория графов"

на тему "Исследование графов"

для студентов специальностей

220200 Автоматизированные системы обработки информации и управления,

220300 Системы автоматизированного проектирования,

направления 552800 Информатика и вычислительная техника

Форма обучения очная и заочная

 

 

Ижевск 2004

 

 

Кафедра "Автоматизированные системы обработки информации и управления".

 

 

Составитель: Кучина Татьяна Леонидовна, ст. преподавателькаф. АСОИУ.

 

Методические указания составлены на основании государственного образовательного стандарта высшего профессионального образования и утверждены на заседании кафедры

Протокол от "____" ________________ 200__ г. № ______.

 

 

Заведующий кафедрой ____________________ В.Н. Кучуганов

 

"____" ________________ 200__ г.

 

СОГЛАСОВАНО:

 

Председатель учебно-методической комиссии

по специальности ____________________ В.Н. Кучуганов

 

"____" ________________ 200__ г.

 

 

Методические указания предназначены для выполнения курсового проекта по дисциплинам:

- "Моделирование систем", "Моделирование и оптимизация" студентами специальности 220200 Автоматизированные системы обработки информации и управления очного и заочного отделения и студентами направления 552800 Информатика и вычислительная техника (бакалавриат);

- "Модели и методы анализа проектных решений", "Моделирование и оптимизация" студентами специальности 220300 Системы автоматизированного проектирования очного и заочного отделения;

 

Начальник учебно-инженерного отдела ____________________ А.М. Ефимова

 

"____" ________________ 200__ г.

 

СОДЕРЖАНИЕ

 

1. ЦЕЛЬ РАБОТЫ…………………………………………………………………….. 3

2. ЗАДАНИЕ НА ВЫПОЛНЕНИЕ РАБОТЫ………………………………………. 3

3. ПРИМЕР ВЫПОЛНЕНИЯ РАБОТЫ…………………………………………….. 3

4. ТРЕБОВАНИЯ К СОДЕРЖАНИЮ И ОФОРМЛЕНИЮ ОТЧЕТА ……………. 15

5. ЛИТЕРАТУРА ……………………………………………………………………… 15

ПРИЛОЖЕНИЕ 1. НАПРАВЛЕННЫЕ ГРАФЫ……………………………….. 16

ПРИЛОЖЕНИЕ 2. ВЛОЖЕНИЕ ГРАФОВ ……………………………………… 18

ПРИЛОЖЕНИЕ 3. ПЛОСКАЯ УКЛАДКА ГРАФА В УЗЛЫРЕШЕТКИ ……. 21

ПРИЛОЖЕНИЕ 4. РАСКРАСКА ГРАФОВ ……………………………………… 23

ПРИЛОЖЕНИЕ 5. ФОРМА ТИТУЛЬНОГО ЛИСТА …………………………... 29

 

  1. ЦЕЛЬ РАБОТЫ

 

Целью работы является закрепление теоретических знаний и проверка уровня усвоения теории по теме «Графы» путем выполнения практической работы.

 

  1. ЗАДАНИЕ НА ВЫПОЛНЕНИЕ РАБОТЫ

 

2.1. Задать произвольный ориентированный (направленный) граф десятого порядка

(с десятью вершинами).

2.2. По заданному графу построить нижний граф.

2.3. Для нижнего графа выполнить следующие операции:

2.3.1. Построить матрицу инцидентности;

2.3.2. Построить матрицу смежности;

2.3.3. Найти цикломатическое число;

2.3.4. Построить базисную цикломатическую матрицу;

2.3.5. Построить цикломатическую матрицу;

2.3.6. Определить толщину графа;

2.3.7. Выделить планарные подграфы;

2.3.8. Сделать плоскую укладку выделенных планарных подграфов в узлы прямоугольных решеток;

2.3.9. Раскрасить вершины и ребра графа.

2.4. Определить диаметр ориентированного графа. Найти количество компонент сильной связности.

 

3. ПРИМЕР ВЫПОЛНЕНИЯ РАБОТЫ

 

 

3.1. Исходный ориентированный граф G приведен на рис.3.1.

 

Рис. 3.1

 

 

3.2. Нижний граф (приложение 1) приведен на рис. 3.2.

Рис. 3.2

 

3.3.1. Матрица инцидентности

Запишем множества всех вершин и всех ребер, соединяющих вершины графа.

Множество вершин:

V ={1,2,3,4,5,6,7,8,9,10}

 

 

Множество ребер:

Е ={{1,5},{5,6},{6,7},{7,4},{4,10},{10,9},{9,8},{8,1},{1,2},{2,3},{3,4},{2,6},

{6,3},{2,9},{3,9},{3,10},{2,8}}.

 

Построим матрицу инцидентности А, считая, что в строках находятся номера вершин, а в столбцах – ребра графа /1/. Будем ставить’1’, если вершина vi инцидентна ребру е , ставить ’0’, если вершина v i не инцидентна ребру е j (табл. 3.1).

Таблица 3.1

  a b c d e f g h i j k l m n o p q
                                   
                                   
                                   
                                   
                                   
                                   
                                   
                                   
                                   
                                   

 

 

3.3.2. Матрица смежности

 

Построение матрицы смежности S проведем для не взвешенного графа G таким образом: если две вершины v i и vj соединены между собой, тогда элементу матрицы смежности sij присвоим ’1’, иначе элементу матрицы смежности sij присвоим ’0’ (табл.3.2).

 

Таблица 3.2

                     
                     
                     
                     
                     
                     
                     
                     
                     
                     
                     

 

3.3.3. Цикломатическое число

Цикломатическое число ν (G) равно числу хорд любого остова в графе G, если связный граф имеет n вершин и m ребер /1/:

n (G) = m - n +1

Если граф G содержит k компонент связности, то его цикломатическое число

 

ν (G) = m - n + k

 

Наш граф содержит одну компоненту связности, поэтому будем искать цикломатическое число по формуле ν(G) = m - n +1.

 

n =10 (количество вершин)

m =17 (количество ребер)

 

ν(G) = m - n +1=17-10 +1=8

т.е. в графе содержится 8 базисных циклов.

 

 

3.3.4. Базисная цикломатическая матрица

В предыдущем пункте мы выяснили, что число базисных циклов равно цикломатическому числу и равно 8.

Для построения базисной цикломатической матрицы БЦМ нам необходимо выделить остов D графа G (рис. 3.3).

 

 

Остов D

Рис. 3.3

 

Теперь можно составить БЦМ (табл. 3.3). В качестве хорды будут выступать те ребра графа G, которые мы удалили для получения остова D. Все остальные ребра будут составлять остов.

Таблица 3.3

 

Хорды Остов D
l m d e q p o n a b c i j k h g f
R1                                  
R2                                  
R3                                  
R4                                  
R5                                  
R6                                  
R7                                  
R8                                  

 

3.3.5. Цикломатическая матрица

 

Для построения цикломатической матрицы C (G) условимся, что каждому элементу матрицы c ij взаимно однозначно сопоставляется вектор-строка:

 

1, если j -ое ребро входит в i -й цикл

c ij =

0, в противном случае

 

Графу G отвечает 17- компонентный вектор a = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1).

Всякий вектор может быть представлен линейной комбинацией базисных векторов. Следовательно, вектор a может быть разложен в поле чисел по mod (2) по своим базисным циклам /2/.

Для построения всего множества циклов графа G необходимо будет выполнить (2ν – ν-1) раз операцию сложения по модулю 2 над базисными циклами, где ν – это цикломатическое число графа. Поэтому для нашего графа эту операцию необходимо провести (28-8-1) раз, т.е. 247 раз.

В общем случае не все графы поддаются бинарному разложению, поэтому для разложения графов по их выделенным базисным компонентам можно использовать операции по mod (3), mod (4) или вообще без модуля / 2 /.

В табл. 3.4 приведена часть цикломатической матрицы C (G).

Таблица 3.4

 

  a b c d e f g h i j k l m n o p q
R1                                  
R2                                  
R3                                  
R4                                  
R5                                  
R6                                  
R7                                  
R8                                  
R9                                  
R10                                  
R11                                  

 

В матрице показаны базисные циклы R1 – R8, которые в совокупности включают в себя все ребра графа G. Циклы R9, R10, R11 получены как линейная комбинация базисных векторов по модулю 2

 

R9 = R1 R2

R10 = R8 R7

R11 = R4 R6

 

 

3.3.6. Толщина графа

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

 

 

 

где S i – степень i -й вершины; n – количество вершин.

 

 

Определим степень каждой вершины, т.е. количество ребер, инцидентных данной вершине (табл. 3.5).

 

Таблица 3.5

 

Номер вершины Степень вершины
   
   
   
   
   
   
   
   
   
   

 

Имеем

       
   


34 - 2

t (G)≥1+ = 1+ 2/3 =1

6*(10 -2)

 

 

Поэтому минимальная толщина графа равна 1.

 

3.3.7. Выделение планарных подграфов

 

В нашем графе ни одно ребро не пересекается с другим, кроме как в вершинах

графа (рис 3.4).

 

 

Рис. 3.4

 

 

Согласно теореме Понтрягина /1/, граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного F5 или K3,3 (приложение 2). Мы видим, что исходный граф не содержит подграфы, гомеоморфные F5 или K3,3, поэтому он планарный.

 

 

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

Граф называется планарным, если его можно уложить на плоскости. Плоский граф – это граф, уже уложенный на плоскости /2/.

 

В пункте 3.3.7 отмечено, что исследуемый граф G является планарным графом.

В графе G заданы только элементные вершины.

 

Рассчитаем число горизонтальных (m) и вертикальных (n) линий в прямоугольной решетке (приложение 3); m и n определяются как минимальные величины, удовлетворяющие следующим условиям /3/:

 

m * n ≥ | V | -площадь решетки;

 

2 * (m + n)- 4 ≥ 0 - число внешних контактных площадок;

 

mnm +1 – квадратичность решетки.

 

       
   
 
 


m * n ≥ 10 m*n ≥ 10 m*n ≥ 10

2*(m+n)-4 ≥ 0 m+n ≥ 2 m ≥ 1

m ≤ n ≤ m+1 m ≤ n m ≤ n

n ≤ m+1 n ≤ m+1

 

 

Возможные значения m, n, m*n приведены в табл.3.6.

 

 

Таблица 3.6

 

m            
n            
m*n            

 

Произведение m на n больше 10 при m = 3 и n = 4. Следовательно, решетка будет содержать 3 горизонтальных линии и 4 – вертикальных.

 

 

Один из вариантов плоской укладки планарного графа в узлы прямоугольной решетки показан на рис. 3.5.

 

 

Рис 3.5

 

 

3.3.9. Раскраска вершин и ребер графа

 

Осуществим раскраску вершин так, чтобы инцидентные вершины были разных цветов, но при этом количество цветов должно быть минимальным /2,4,5/. Аналогично раскрашиваем и ребра графа G (рис. 3.6).

 

Рис 3.6

 

 

3.4. Определение диаметра ориентированного графа. Нахождение количества компонент сильной связности

 

 

Исходный ориентированный граф изображен на рис. 3.7.

 

Рис. 3.7

 

 

Составим матрицу смежности S (G) (табл. 3.7). Для этого в строках и столбцах отметим все вершины графа G. Построение матрицы смежности S проведем теперь для ориентированного графа G таким образом: если две вершины vi и vj соединены между собой, тогда элементу матрицы смежности sij присвоить ту дугу, для которой вершина vi является началом, а вершина vj концом.

 

Таблица 3.7

Матрица смежности S (G)

                     
    i     a     h    
      j     l   n o  
        k            
                    e
            b        
      m       c      
        d            
                  g  
      p             f
      q              

 

Граф называется сильно связным, если любая пара вершин соединена путем /1/.

Максимальный по включению вершин сильно связный подграф графа называется его компонентой сильной связности. Граф называется несильно связным, если число его компонент сильной связности больше 1.

Теперь мы можем воспользоваться теоремой, которая говорит, что граф состоит из k компонент связности тогда и только тогда, когда его матрица достижимости является k -клеточной.

Матрица А называется k - клеточной, если в результате перестановки строк и столбцов она приводится к виду, показанному в табл. 3.8, где подматрица А , i = 1, …. k, не содержит ни одного нулевого элемента (кроме, быть может, диагональных).

 

Таблица 3.8

 

А      
  А    
    А  
      А

 

Максимальная степень, в которую необходимо возвести матрицу смежности, равна диаметру графа. Его можно определить так:

 

d(G)=max min l (vi,vj), где l -длина дуги от vi до vj вершины.

j i

Диаметр нашего графа оказался равен 4. Найдем матрицу достижимости по формуле:

D(G)=

где S(G)-матрица смежности;

i=1…d(G);

d(G)- диаметр графа;

Для нашего графа S2 (G)+ S3 (G)+ S4 (G)

Составим матрицы S2 (G) (табл. 3.9), S3 (G) (табл. 3.10), S4 (G) (табл. 3.11).

При возведении в n -ю степень матрицы смежности S= умножение рассматриваем как конкатенацию – приписывание справа к идентификатору, соответствующему i -ой строке, идентификатора, соответствующего j – му столбцу, суммирование – как объединение полученных в результате умножения слов.

 

Таблица3.9

Матрица S2 (G)

                     
      ij     il,ab   in io,hg  
      lm,op jk     lc   ng of
                    ke
      eq              
      bm       bc      
        mk,cd            
                    de
      gp             gf
      fq pk            
        qk            

 

 

Таблица 3.10

Матрица S3 (G)

                     
      ilm, iop, abm, hgp ijk     ilc, abc   ing iof, hgf
      ngp, ofq lmk, lcd, opk           jke, ngf
      keq              
        eqk            
        bmk, bcd            
                    mke, cde
      deq              
      gfq gpk            
      o fqk           pke
                    qke

 

 

Таблица 3.11

Матрица S4 (G)

                     
      ingp, iofq, hgfq ilmk, ilcd, iopk, abmk, abcd, hgpk           ijke, ingf
      jkeq, ngfq ngpk, ofqk           lmke, lcde, opke
        keqk            
                    eqke
                    bmke, bcde
      mkeq, cdeq              
        deqk            
        gfqk           gpke
      pkeq             fqke
      qkeq              

 

Составим матрицу достижимости D(G) (табл.3.12).

 

Таблица 3.12

Матрица достижимости D(G)

 

                     
    i ij, ilm, iop, abm, hgp ingp, iofq, hgfq ijk, ilmk, ilcd, iopk, abmk, abcd, hgpk a il, ab ilc, abc h, in io, hg, ing iof, hgf, ijke, ingf
      j, lm, op, ngp, ofq jkeq, ngfq jk, lmk, lcd, opk ngpk, ofqk   l lc n o, ng of, jke, ngf, lmke, lcde, opke
      keq k, keqk           ke
      eq eqk           e, eqke
      bm bmk, bcd   b bc     bmke, bcde
      m, mkeq, cdeq mk, cd     c     mke, cde
      deq d, deqk           de
      gp, gfq gpk, gfqk         g gf, gpke
      p, fq, pkeq pk, fqk           f, pke, fqke
      q, qkeq qk           qke

 

 

Суммируя S, S2, S3, S4 получаем, что в результирующей матрице достижимости D(G) присутствуют нулевые элементы. Это означает, что не для всех вершин нашего графа существуют цепи длиной 1, 2, 3, 4. Наш ориентированный граф не является сильно связным, так как граф называется сильно связным, если любая пара его вершин соединена путем. Мы видим, что, например, вершина 7 не соединена путем с вершиной 9.

Найдем количество компонент сильной связности. Компоненте сильной связности в матрице достижимости соответствует подматрица максимального размера, каждый элемент которой не равен нулю. В данной матрице имеем 1 компоненту сильной связности с носителем {3, 4, 10}.

 

 

4. ТРЕБОВАНИЯ К СОДЕРЖАНИЮ И ОФОРМЛЕНИЮ ОТЧЕТА

 

Отчет должен включать:

- задание на выполнение работы;

- описание этапов выполнения работы в соответствии с заданием;

- выводы по работе;

- перечень использованной литературы.

Работа должна быть оформлена в соответствии с требованиями ГОСТов /6/.

Форма титульного листа дана в приложении 5.

 

5. ЛИТЕРАТУРА

 

1. Горбатов В.А. Основы дискретной математики - М.: Высшая школа, 1986

2. Акимов О.Е. Дискретная математика - М.: Лаборатория Базовых Знаний, 2001

3. Абрайтис Л.Б. Автоматизация проектирования топологии цифровых интегральных

микросхем – М.: Радио и связь, 1985

4. Харари Ф. Теория графов– М.: Мир, 1973

5. Кристофидес Н. Теория графов, алгоритмический подход – М.: Мир, 1978

6. Соболева Н.В. Методические указания по оформлению курсовых работ, курсовых

и дипломных проектов - Ижевск: ИжГТУ, 2003

7. Новиков Ф.А. Дискретная математика для программистов – Санкт-Петербург:

Питер, 2001

 

 

ПРИЛОЖЕНИЕ 1

НАПРАВЛЕННЫЕ ГРАФЫ

 

Направленный (ориентированный) граф D состоит из конечного непустого множества вершин V=VD и конечного множества направленных рёбер E=ED, которые производят отображение δ: E→V×V. Если δ (e) = (υ, ω), то υ называется начальной вершиной, а ω - конечной вершиной ребра e /2/.

Для направленного графа D можно путём отмены направленности рёбер получить соответствующий ненаправленный граф Г, который называется нижним для графа D. Формально, нижний для графа D граф имеет те же вершины и рёбра, но последний утрачивает свою направленность.

Направленный граф называется простым, если он не содержит петель (т. е рёбер e, для которых δ (e) = (υ, υ)) и не содержит множественных рёбер (т.е с одинаковыми начальной и конечной вершинами).

На рис. П1.1 показаны простой направленный и нижний для него графы. Два ребра направленного графа, связывающие вершины υ4 и υ5, не являются множественными, так как их направления различны, т.е у них разные начальные и конечные вершины. В то же время, соответствующий нижний граф не является простым, так как он имеет множественные рёбра.

 

рис. П1.1

 

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

Элемент (i, j) матрицы смежности направленного графа представляет собой число рёбер с начальной вершиной υi и конечной вершиной υj, поэтому матрица может и не быть симметричной.

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

Для направленного графа последовательностью направленных рёбер из υ0 в υn называется последовательность рёбер e1,e2, …,en таких, что δ(ei) = (υi-1i) для i =1,2,…, n.

Направленный граф называется связным (или слабо связным), если его нижний ненаправленный граф является связным. Направленный граф называется сильно связным, если для каждой упорядоченной пары вершин (υ,ω) существует направленный путь

из υ в ω.

 

 

Пример. На рис. П1.2 показаны направленные графы, у которых одинаковые нижние ненаправленные графы. Граф (а) не является сильно связным, так как, например, нет пути из υ в ω, или, формально, мы не можем перейти из υ в ω вдоль рёбер в направлении стрелок. Граф (b) является сильно связным, так как мы можем перейти из любой вершины в любую другую вершину в результате движения вдоль стрелок рёбер.

 

ω  

ω

(а) (b)

 

 

Рис. П1.2

 

ПРИЛОЖЕНИЕ 2

 

ВЛОЖЕНИЕ ГРАФОВ

 

Определим, является ли граф планарным, можно ли осуществит



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-02 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: