Методические рекомендации (стр. 8 )

Табл. 3

G1
a	1,2
b	2,2
c	2,3
d	3,3
e	3,5
f	1,4
g	4,5

G2
a	1,2
b	2,3
c	3,4
d	4,5
e	1,1
f	1,5
g	55

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

Для проверки изоморфности графов G1 и G2 по матрице инцидентности (и списку рёбер) требуется осуществить всевозможные перестановки строк и столбцов матрицы G1, чтобы проверить, получается ли в результате пары перестановок и матрица инцидентности, соответствующая графу G2. Maксимальное число перестановок равно n! m! = 5!×7!, поэтому решение задачи таким способом не менее трудоемко.

Однако в нашем случае по графическим представлениям G1и G2 нетрудно обнаружить сходство графов.

Для этого достаточно на рис. G2 “поднять” вершину В до условия вершин 2, 4, что позволяет обнаружить изоморфность графов.

Таким образом, графы G1 и G2 изоморфны и отличаются только нумерацией.

Нетрудно определить требуемые перенумерации вершин и рёбер графа G2, позволяющие перейти от матриц инцидентности, смежности или списка рёбер графа G1 к соответствующим представлениям графа G2:

и .

6) Задать графы G1 – G3 , изображенные на рис.1, матрицами инцидентности и смежности, а также списком ребер.

7) Задать различными способами графы G1 – G7, определённые ниже. Проверить справедливость сформулированных в примере 3 правил переходов от одного способа задания графа к другому:

а) G1 – тетраэдр;

б) G2 – тетраэдр с петлями во всех вершинах;

в) G3 – куб;

г) G4 –граф, представленный на рис.4а;

д) G5 – граф на рис.4б;

е) G6 – граф на рис.4в;

ж) G7 – граф на рис.4г.

 

Рис. 4

8) Построить матрицы инцидентности и смежности, а также список рёбер для графа G3 (рис. 3). Изоморфен ли граф G3 графам G1 и G2 (рис.3). Проверить по матрицам смежности (или инцидентности) графов.

9)

Рис. 5

Графы (рис.5) задать матрицами смежности. Определить, изоморфны ли эти графы?

10)

Рис. 6.

Показать, что два графа (рис.6) изоморфны.

ЗАДАНИЯ ДЛЯ КОНТРОЛЬНОЙ РАБОТЫ

№ варианта	Р1	Р2	Р3
1	6	4	5
2	7	5	5
3	6	7	5
4	7	5	7
5	6	6	5
6	7	5	4
7	6	4	6
8	7	5	6
9	6	4	5
0	7	6	5

Контрольная работа

1. Определить результаты действий АÈВ, АÇВ, А\В, В\A, А+В:

1.

2. Найти (АÈВ)ÇС и (АÈВ)\С, если

3. Оценить множество

4. Определить истинность или ложность высказываний:

,

,

;

5. В учебной группе студентов. Сколькими способами их можно разбить на бригады по Р1 человек?

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

7. Составить матрицы инцидентности, смежности и список ребер для графов:

Литература

Теория множеств:

1.  Александров в общую теорию множеств, огл 3, гостех издат, 1948.

2.  Дени- Современная математика, Мир, М, 1966.

3.  Современные основания общей теории систем.

4.  Мышкис по высшей математике.

5.  , , Курс дискретной математики, 1992.

Элементы математической логики:

1.  Эдельман логика. М.: Высшая школа, 1975.

2.  , Драгалин в математическую логику. М.: Изд - во МГУ, 1982.

3.  , Осипова дискретной математики. М.: Изд-во МАИ, 1992.

4.  Новиков математической логики. М.: Наука, 1973.

Элементы комбинаторики. Бином Ньютона.

1.  Ф. Мостеллер, Р. Рурке, Дж. Томас. Вероятность. Изд - во Мир, М.: 1969.

2. . Алгебра, II ч.: 1957.

Теория графов:

1.  Москинова математика. М.: Логос. 2002.

2.  О. Оре. Графы и их применение. М.: Мир. 1965.

3.  К. Берж. Теория графов и ее применение. М.: Ин. литер. 1962.

4.  Новиков математика (для программистов). М.: Питер. 2000.