Решение

Изображение графа представлено на рис. 28.

Рис. 28

Так как у графа пять вершин, то матрица смежности будет :

Вопросы и задачи для самостоятельного решения

1. Перечислите способы представления графов. Дайте понятия матриц смежности и инцидентности.

2. Постройте граф по данной матрице смежности:

 

3. Для следующих графов найдите матрицы инцидентности и смежности (рис. 29, a, б):

 

б

а

Рис. 29

 

3. Пронумеруйте вершины и ребра орграфов (рис. 30, а, б). Найдите для них матрицы инцидентности и смежности.

4. Можно ли нарисовать, не отрывая карандаша от бумаги и не проходя ни по одному их отрезков дважды, «домики с крышами» (рис. 31, а, б, в, г, д)?

б

а

 

Рис. 30

б

в

а

д

г

 

Рис. 31

 

3.3. Связность графов

Определение 1. Граф (орграф) называют подграфом графа (орграфа) , если и .

Будем использовать обозначение , аналогичное обозначению включения для множеств.

Определение 2.Если хотя бы одно из указанных двух включений в определении 1 строгое, то называют собственным подграфом графа.

Например,графы на рис. 32 являются подграфами графа на рис. 33.

 

Рис. 32

 

Рис. 33

 

Определение 3.Подграф называют максимальным подграфом, если он не является собственным подграфом никакого другого подграфа .

Например,на рис. 34 графы – максимальные подграфы графа , причем они также являются собственными подграфами.

 

 

Рис. 34

 

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

Например,граф на рис. 33 является связным.

Определение 5. Орграф называется сильно связным, если для любых двух его вершин и вершина достижима из вершины и вершина достижима из (т. е. между ними существует путь). Если существует путь из вершины в или из в , то орграф – односторонне связан. Орграф называется слабо связным, если в графе существует цепь между вершинами и w ( – граф, полученный из первоначального орграфа после отмены ориентации ребер).

Определение 6. Орграф, не являющийся слабо связным, называется несвязным.

Например,на рис. 35: а – сильная связность; б – односторонняя связность; в – слабая связность.

а

в

б

 

Рис. 35

 

Определение 7. Компонентой связности графа называется его связный подграф, не являющийся подграфом никакого другого связного подграфа графа .

аб Рис. 36

Определение 8. Компонентой сильной связности (слабой связности) орграфа называется его связной подграф, не являющийся подграфом никакого другого cильного (слабого) связного подграфа графа .

Например, граф, изображенный на рис. 36, а, имеет две компоненты связности (рис. 36, б).

Орграф (рис. 37, а) имеет три компоненты связности (рис. 37, б).

 

б

а

Рис. 37

 

Теорема.Пусть дан граф , у которого – число вершин, – число ребер, – число компонент связности графа. Тогда .

Следствие. Если , то граф связен.

Вопросы и задачи для самостоятельного решения

1. Сформулируйте понятие связного графа (орграфа).

2. Для графов, изображенных на рис. 38, а, б, постройте по четыре подграфа.

б

а

Рис. 38

 

3. Определите связные орграфы. Какие из них являются сильно связными (рис. 39)?

 

в

а

б

 

Рис. 39

4. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

4.1. Перестановки, размещения и их количество

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

Определение 1. Пусть имеется элементов , отличающихся друг от друга какими-то признаками, например, номерами, названиями, индексами и т. д. Назовем эту совокупность генеральной совокупностью.

Определение 2. Произвольное упорядоченное множество элементов , составленное из элементов генеральной совокупности, называется выборкой объема .

Правило суммы. Пусть объект можно выбрать способами, объект можно выбрать способами. Тогда выбор либо объекта , либо объекта можно осуществить способами.

Пример 1. Студент выбирает какую-либо одну книгу на полке, где находятся 20 различных учебников по математике, 15 учебников по информатике и 10 учебников по химии. Тогда существуют 20 + 15 + 10 = 47 различных вариантов выбора книги.

Правило произведения. Пусть объект можно выбрать способами, объект можно выбрать способами. Тогда выбор пары и можно осуществить способами.

Пример 2. Из города в город ведут 5 дорог, а из города до города ведут 4 дороги. Следовательно, количество путей, ведущих из в и проходящих через город , равно .

Рассмотрим группы элементов, называемые перестановками, размещениями и сочетаниями.

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

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

Каждая перестановка содержит все элементов множества, и различные перестановки отличаются только порядком элементов.

Число перестановок из элементов обозначается , где – первая буква от английского слова permutation – перестановка.

Определение 4. Произведение подряд идущих натуральных чисел от 1 до некоторого называется факториалом целого положительного числа и обозначается . Таким образом, . Принято считать, что .

Пример 3. Сколько различных четырехзначных чисел можно составить из цифр 1, 2, 5, 8 при условии, что цифры в числе не повторяются?

Решение

Количество различных четырехзначных чисел из данных цифр равно числу перестановок из четырех элементов .

Пример 4. Найти , если .