Тема 8. Характеристические числа графов

Цикломатическим числом графа G называется число ребер, которые надо убрать, что бы граф стал ацикличным [4, 5].

Цикломатическое число графа G находится по формуле:

, (8.1)

число вершин,

число ребер,

число компонент связности.

Замечание: Если цикломатическое число графа равно 1, то в графе ровно 1 цикл.

Внутренне устойчивым множеством графа G называется множество вершин S, все вершины которого попарно несмежны.

Число внутренней устойчивости:

. (8.2)

Внешне устойчивым множеством графа G называется множество вершин Q, таких, что из всех вершин множества ведут ребра в вершины множества Q.

Число внутренней устойчивости:

. (8.3)

Граф G называется h -хроматическим, если его вершины можно раскрасить h различными красками так, чтобы никакие две смежные различные вершины не были окрашены в один цвет. Хроматическое число графа– это наименьшее число таких красок.

Граф G называется k -раскрашиваемым, если его ребра можно раскрасить k различными красками так, чтобы никакие два смежных ребра не были окрашены в один цвет. Хроматический индекс графа – это наименьшее число таких красок.

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

Пример 8.1.

Для графа, приведенного на рисунке 8.1, найти все характеристические числа.

Рис. 8.1. Нахождение характеристических чисел графа

Решение.

Характеристическими числами графа называются:

1) цикломатическое число, 2) число внутренней устойчивости, 3) число внешней устойчивости, 4) хроматическое число, 5) хроматический индекс.

1) Для нахождения цикломатического числа необходимо выяснить, сколько ребер графа достаточно убрать, чтобы разрушить все существующие циклы. Из рисунка 8.2 видно, что таких ребер минимум 5. Они указаны пунктиром.

Рис. 8.2. Нахождение цикломатического числа графа

Этот же результат можно получить по формуле (8.1).

Здесь число компонент связности графа. Так как все вершины графа связны (связаны маршрутами), то у этого графа 1 компонента связности.

2) Для нахождения числа внутренней устойчивости, необходимо выяснить, каким будет максимальное внутренне устойчивое множество графа.

Рис. 8.3. Нахождение числа внутренней устойчивости графа

Для этого надо определить максимальную совокупность попарно несмежных вершин. Из рисунка 8.3 видно, что таких вершин максимум 3. Они помечены кружком на рисунке 8.3.

Таким образом, максимальным внутренне устойчивым множеством будут множества вершин S ₁ = {2, 5, 7}, S ₂ = {1, 6, 3}.

Тогда по формуле (8.2) получим число внутренней устойчивости:

3) Для нахождения числа внешней устойчивости, необходимо выяснить, каким будет минимальное внешне устойчивое множество графа.

Рис. 8.4. Нахождение числа внешней устойчивости графа

На рисунке 8.4 видно, что вершины множества Q ₁ = {4, 3} таковы, что из остальных вершин графа, составляющих множество , ведут ребра в вершины 4 или 3. Значит множество Q ₁ – это множество внешней устойчивости. Очевидно, что таким же свойством обладает множество Q ₂ = {4, 7}. Оба этих множества минимальны, то есть множества из одной вершины, обладающего указанным свойством, найти нельзя.

Тогда по формуле (8.3) получим число внешней устойчивости:

4) Для нахождения хроматического числа, необходимо выяснить, каким будет минимальное количество красок, в которые можно раскрасить вершины графа, так чтобы никакие две смежные вершины не были окрашены в один цвет.

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

На рисунке 8.5 видно, что вершины 2, 5 и 7 – попарно несмежны, значит, их можно раскрасить в один и тот же цвет (например, красный). Он помечен звездочками.

Рис. 8.5. Нахождение хроматического числа графа

Далее, множество несмежных вершин составляют вершины 1, 6 и 3. Значит, они тоже могут быть раскрашены в один цвет (например, голубой). Он помечен треугольниками.

Очевидно, что вершину 4 нельзя раскрасить ни в красный, ни в голубой цвета. Для нее придется использовать третий цвет (например, зеленый). Он помечен кружком.

Таким образом, минимальное количество цветов – 3. Значит хроматическое число графа .

5) Для нахождения хроматического индекса, необходимо выяснить, каким будет минимальное количество красок, в которые можно раскрасить ребра графа, так чтобы никакие два смежных ребра не были окрашены в один цвет.

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

Рис. 8.6. Нахождение хроматического индекса графа

На рисунке 8.6 видно, что вершина 4 имеет самое большое из всех количество инцидентных ребер. Поэтому k = 4.

Тогда по теореме Визинга хроматический индекс подчиняется условию:

Осталось определить, достаточно ли четырех цветов для указанной раскраски ребер, или потребуется пять.

Возьмем вершину 4 и раскрасим все инцидентные ей ребра в разные цвета. Например, в красный, зеленый, синий и желтый. На рисунке 8.6 они помечены соответственно одной чертой, двумя чертами, тремя чертами и волной.

Далее, распределяем указанные цвета на оставшихся не раскрашенными ребрах, учитывая то, что смежные ребра не могут быть окрашены в один цвет.

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

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ

1. Индивидуальные задания по теме «Множества»

Задание 1

Дано универсальное множество U и множества A, B и C. Найти множество D. Записать ответ в виде списка.

Вариант 1

;

D = .

Вариант 2

;

D = .

Вариант 3

;

D = .

Вариант 4

;

D = .

Вариант 5

;

D = .

Вариант 6

;

D = .

Вариант 7

;

D = .

Вариант 8

;

D = .

Вариант 9

;

D = .

Вариант 10

;

D = .

Вариант 11

;

D = .

Вариант 12

;

D = .

Вариант 13

;

D = .

Вариант 14

;

D = .

Вариант 15

;

D = .

Задание 2

На диаграмме Вьенна-Эйлера изобразить результат действия:

Вариант 1 .

Вариант 2 .

Вариант 3 .

Вариант 4 .

Вариант 5 .

Вариант 6 .

Вариант 7 .

Вариант 8 .

Вариант 9 .

Вариант 10 .

Вариант 11 .

Вариант 12 .

Вариант 13 .

Вариант 14 .

Вариант 15 .

2. Индивидуальные задания по теме «Векторы и прямые произведения множеств. Проекция вектора на ось»

Задание 1

Даны множества A, B и C. Найти прямые произведения

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Вариант 11

Вариант 12

Вариант 13

Вариант 14

Вариант 15

Задание 2

Дано множество векторов V. Найти проекции векторов и векторного множества на оси:

Вариант 1 .

Вариант 2 .

Вариант 3 .

Вариант 4 .

Вариант 5 .

Вариант 6 .

Вариант 7 .

Вариант 8 .

Вариант 9 .

Вариант 10 .

Вариант 11 .

Вариант 12 .

Вариант 13 .

Вариант 14 .

Вариант 15 .

3. Индивидуальные задания по теме «Комбинаторика»

Вариант 1

1. В аквариуме 13 рыбок, из них 5 красных. Наугад выбирают 4. Сколькими способами это можно сделать так, чтобы среди выбранных рыбок была ровно 1 красная?

2. Сколько способов выбрать из 10 человек команды 3 человека для бега на дистанцию 1000 м?

Вариант 2

1. На прилавке 11 банок рыбных консервов. Из них – одна испорчена. Наугад выбирают 4. Сколькими способами это можно сделать так, чтобы среди выбранных банок попалась испорченная?

2. Сколько способов составить слово БАРБАРА из карточек разрезной азбуки слова АБРАКОДАБРА, выбирая их случайным образом?

Вариант 3

1. В темном погребе 10 банок с огурцами. Из них 3 – помутнели. Наугад выбирают 3 банки. Сколькими способами это можно сделать так, чтобы среди выбранных банок была ровно 1 помутневшая?

2. Сколько способов составить слово СПОРТ из карточек разрезной азбуки слова ОБОРОНОСПОСОБНОСТЬ, выбирая их случайным образом?

Вариант 4

1. В корзинке 13 опенков, из них 4 ложных. Наугад выбирают 7 опят. Сколькими способами это можно сделать так, чтобы среди выбранных грибов было ровно 2 ложных?

2. Сколько способов выбрать 3 человека для участия в эстафете на 200, 300 и 400 м из 10 человек команды?

Вариант 5

1. В ведерке 10 зернышек, из них 3 не взойдут. Наугад выбирают 5 для посадки. Сколькими способами это можно сделать так, чтобы среди выбранных зернышек взойдут ровно 2?

2. Сколько способов составить слово БРАК из карточек разрезной азбуки слова АБРАКОДАБРА, выбирая их случайным образом?

Вариант 6

1. В коробке 12 карандашей, 10 цветных и 2 простых. Наугад выбирают 3. Сколькими способами это можно сделать так, чтобы среди выбранных карандашей было ровно 2 цветных?

2. Сколько способов выбрать из 6 шаров 2 – один для Маши, а другой для Вити?

Вариант 7

1. В колхозном гараже 4 трактора и 3 сеялки. Наугад выбирают 4 машины. Сколькими способами это можно сделать так, чтобы среди выбранных было ровно 3 трактора золотых?

2. Сколькими способами можно набрать последние 3 цифры телефонного номера?

Вариант 8

1. В курятнике 11 куриц, из них 7 рябок, остальные белые. Наугад выбирают 4. Сколькими способами это можно сделать так, чтобы среди выбранных куриц было ровно 3 белых?

2. Сколько способов составить слово АБРАКОДАБРА из карточек разрезной азбуки, переставляя их случайным образом?

Вариант 9

1. В хлеву 9 коров, из них 6 доятся. Наугад выбирают 3. Сколькими способами это можно сделать так, чтобы среди выбранных рыбок было ровно 2 доящихся коровы?

2. Сколько способов составить из букв слова «МИШЕНЬ» различных слов?

Вариант 10

1. Сколькими способами можно из 6 стандартных и 5 нестандартных болтов выбрать 3, так чтобы среди них было 1 стандартны1 и 2 нестандартных?

2. Сколькими способами можно посадить 6 различных цветов в 6 разных цветочных горшков?

Вариант 11

1. Сколькими способами можно из 4 стандартных и 5 нестандартных деталей выбрать 4, так чтобы среди них было 2 стандартные и 2 нестандартные?

2. Сколькими способами можно расставить на 6 путях 4 состава?

Вариант 12

1. В клетке 8 мышей, из них 4 белых. Наугад выбирают 3. Сколькими способами это можно сделать так, чтобы среди выбранных мышей было ровно 2 белых?

2. Сколькими способами можно из 15 человек класса выбрать культорга, физорга и профорга?

Вариант 13

1. В аквариуме 7 рыбок, из них 5 золотых. Наугад выбирают 3. Сколькими способами это можно сделать так, чтобы среди выбранных рыбок было ровно 2 золотых?

2. Сколько способов выбрать из 6 шаров 2 без учета порядка?

Вариант 14

1. В ящике 7 деталей, из них 3 стандартных. Наугад выбирают 3. Сколькими способами это можно сделать так, чтобы среди выбранных деталей было ровно 2 стандартных?

2. Сколькими способами можно из букв a, b, c, d составить слов длины 5?

Вариант 15

1. В аквариуме 9 рыбок, из них 4 золотых. Наугад выбирают 3. Сколькими способами это можно сделать так, чтобы среди выбранных рыбок было ровно 2 золотых?

2. Сколькими способами можно в кинотеатре рассадить 6 человек на ряд из 18 мест?

4. Индивидуальные задания по теме «Соответствия»

Соответствие G является подмножеством прямого произведения множеств A и B. Определить свойства соответствия. Является ли оно функцией? Отображением? Почему? Если G – отображение, то оно является отображением А в В или А на В. Является ли оно взаимно однозначным?

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Вариант 11

Вариант 12

Вариант 13

Вариант 14

Вариант 15

5. Индивидуальные задания по теме «Отношения»

Построить матрицу бинарного отношения, определить свойства отношения. Является ли оно отношением эквивалентности? Порядка? Если R – отношение эквивалентности, то указать разбиение на классы эквивалентности и определить индекс разбиения. Если R – отношение порядка, то указать строгий порядок или не строгий, полный или не полный (почему?)

Вариант 1

На множестве чисел задано отношение .

Вариант 2

На множестве натуральных чисел задано отношение R – «быть меньше». Построить матрицу бинарного отношения на первых шести элементах натурального ряда.

Вариант 3

На множестве чисел задано отношение .

Вариант 4

На множестве чисел задано отношение .

Вариант 5

На множестве натуральных чисел задано отношение R – «иметь общий делитель, отличный от 1». Построить матрицу бинарного отношения на первых шести элементах натурального ряда.

Вариант 6

На множестве слов задано отношение .

Вариант 7

На множестве слов задано отношение

Вариант 8

На множестве натуральных чисел задано отношение R – «быть больше или равно». Построить матрицу бинарного отношения на первых шести элементах натурального ряда.

Вариант 9

На множестве слов задано отношение .

Вариант 10

На множестве слов задано отношение .

Вариант 11

На множестве натуральных чисел задано отношение R – «быть делителем». Построить матрицу бинарного отношения на первых шести элементах натурального ряда.

Вариант 12

Вариант 13

На множестве слов задано отношение .

Вариант 14

На множестве натуральных чисел задано отношение R – «быть больше». Построить матрицу бинарного отношения на первых шести элементах натурального ряда.

Вариант 15

На множестве чисел задано отношение .

6. Индивидуальные задания по теме «Способы задания графов. Локальные степени вершин»

Для графов, приведенного на рисунках а) и б) найти матрицу инцидентности и матрицу смежности. Определить локальные степени вершин. Записать векторы локальных степеней.

Вариант 1

а)

б)

Рис.1

Вариант 2


а)	б)
Рис.2

Вариант 3


а)	б)
Рис.3

Вариант 4


а)	б)
Рис.4

Вариант 5


а)	б)
Рис.5

Вариант 6


а)	б)
Рис.6

Вариант 7


а)	б)
Рис.7

Вариант 8


а)	б)
Рис.8

Вариант 9


а)	б)
Рис.9

Вариант 10


а)	б)
Рис.10

Вариант 11


а)	б)
Рис.11

Вариант 12


а)	б)
Рис.12

Вариант 13


а)	б)
Рис.13

Вариант 14


а)	б)
Рис.14

Вариант 15


а)	б)
Рис.15

7. Индивидуальные задания по теме «Маршруты. Расстояние между вершинами графа. Диаметр и центр графа»

Задание 1. Для графа, приведенного на рисунке, записать 1) маршрут общего вида, 2) не простую цепь, 3) простую цепь, 4) циклический маршрут общего вида,5) не простой цикл, 6) простой цикл.

Задание 2. Построить матрицу расстояний. Найти эксцентриситеты вершин. Определить диаметр и радиус графа. Указать центры графа. Записать диаметральные и радиальные цепи.

Вариант 1

Рис. 16

Вариант 2

Рис. 17

Вариант 3

Рис. 18

Вариант 4

Рис. 19

Вариант 5

Рис. 20

Вариант 6

Рис. 21

Вариант 7

Рис. 22

Вариант 8

Рис. 23

Вариант 9

Рис. 24

Вариант 10

Рис. 25

Вариант 11

Рис. 26

Вариант 12

Рис. 27

Вариант 13

Рис. 28

Вариант 14

Рис. 29

Вариант 15

Рис. 30

8. Индивидуальные задания по теме «Характеристические числа графов»

Для графа, приведенного на рисунке, определить цикломатическое число, число внутренней устойчивости, число внешней устойчивости, хроматическое число, хроматический индекс.

Вариант 1

Рис. 31

Вариант 2

Рис. 32

Вариант 3

Рис. 33

Вариант 4

Рис. 34

Вариант 5

Рис. 35

Вариант 6

Рис. 36

Вариант 7

Рис. 37

Вариант 8

Рис. 38

Вариант 9

Рис. 39

Вариант 10

Рис. 40

Вариант 11

Рис. 41

Вариант 12

Рис. 42

Вариант 13

Рис. 43

Вариант 14

Рис. 44

Вариант 15

Рис. 45

Литература

1. Теория вероятностей и математическая статистика [Текст]: практикум / Кемеровский гос. ун-т; [сост. С. Г. Гутова]. - Кемерово: КемГУ, 2017. - 185 с.: рис., табл.

2. Дискретная математика: учеб.-метод. Пособие [Текст] / ФГБОУ ВПО «Кемеровский государственный университет»; сост. С. Г. Гутова, Т. А. Невзорова. – Кемерово, 2011. – 128 с.

3. Кузнецов, О. П. Дискретная математика для инженера [Текст] / О. П. Кузнецов, Г. М. Адельсон-Вельский. – М.: Энергоатомиздат, 1986. – 480 с.

4. Чуешева, О. А. Математическая логика: учеб.-метод. пособие [Текст] / сост. О. А. Чуешева. – Кемерово, 2006. – 48 с.

5. Щекочихина, С. Г. Дискретная математика: вопросы для самостоятельного изучения для студентов 1 курса МФ спец. 01.02. / [Текст] / С. Г. Щекочихина. – Кемерово: Кузбассвузиздат, 2003. – 64 с.

ГУТОВА Светлана Геннадьевна

ДИСКРЕТНАЯ МАТЕМАТИКА

Часть 1

учебно-методическое пособие