Міністерство освіти і науки Російської Федерації
Курський державний технічний університет
Кафедра ПЗ ОТ та АС
Лабораторна робота № 1
Графи. Основні поняття
Виконав: студент гр. ПО 62 Шіляков І.А.
Перевірив: доцент Томакова Р.А.
Курськ 2007
Завдання:
1. По заданих матрицями суміжності вершин відновити графи.
2. Побудувати для кожного графа матрицю суміжності ребер, інцидентності, досяжності, контрдостіжімості.
3. Знайти і побудувати об'єднання, перетин, кільцеву суму заданих графів.
4. Знайти композицію графів
5. Для кожного графа знайти і побудувати остовних підграф, довільний підграф, породжений пiдграф.
6. Визначити локальні ступеня вершин графа, перевірити чи існує в даному графі ейлерова ланцюг, Ейлером цикл.
7. Визначити хроматичні і Цикломатичне числа даних графів.
8. Знайти всі бази графа.
9. Визначити в кожному графі сильні компоненти зв'язності, побудувати конденсацію графа.
Виконання:
1. По заданих матрицями суміжності вершин відновити графи.
A 1
SHAPE \ * MERGEFORMAT
G 1 (X 1, A 1)
A 2
SHAPE \ * MERGEFORMAT
G 2 (X 2, A 2)
2. Побудувати для кожного графа матрицю суміжності ребер, інцидентності, досяжності, контрдостіжімості.
B 1
B 2
S 1
S 2
R 1 R 2
Курський державний технічний університет
Кафедра ПЗ ОТ та АС
Лабораторна робота № 1
Графи. Основні поняття
Виконав: студент гр. ПО 62 Шіляков І.А.
Перевірив: доцент Томакова Р.А.
Курськ 2007
Завдання:
1. По заданих матрицями суміжності вершин відновити графи.
2. Побудувати для кожного графа матрицю суміжності ребер, інцидентності, досяжності, контрдостіжімості.
3. Знайти і побудувати об'єднання, перетин, кільцеву суму заданих графів.
4. Знайти композицію графів
5. Для кожного графа знайти і побудувати остовних підграф, довільний підграф, породжений пiдграф.
6. Визначити локальні ступеня вершин графа, перевірити чи існує в даному графі ейлерова ланцюг, Ейлером цикл.
7. Визначити хроматичні і Цикломатичне числа даних графів.
8. Знайти всі бази графа.
9. Визначити в кожному графі сильні компоненти зв'язності, побудувати конденсацію графа.
Виконання:
1. По заданих матрицями суміжності вершин відновити графи.
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |
| x 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| x 2 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| x 3 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| x 4 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| x 5 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| x 6 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| x 7 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
|
X 1 |
X 3 |
X 4 |
X 6 |
X 7 |
X 5 |
a 1 |
a 2 |
a 3 |
a 4 |
a 5 |
a 6 |
a 7 |
a 8 |
a 9 |
a 10 |
a 11 |
a 12 |
a 13 |
a 14 |
G 1 (X 1, A 1)
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |
| x 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| x 2 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| x 3 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| x 4 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| x 5 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| x 6 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| x 7 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
|
X 3 |
X 4 |
X 5 |
X 6 |
X 7 |
X 1 |
a 1 |
a 2 |
a 3 |
a 4 |
a 5 |
a 6 |
a 7 |
a 8 |
a 9 |
a 10 |
a 11 |
a 12 |
a 14 |
a 13 |
G 2 (X 2, A 2)
2. Побудувати для кожного графа матрицю суміжності ребер, інцидентності, досяжності, контрдостіжімості.
| а 1 | а 2 | а 3 | а 4 | а 5 | а 6 | а 7 | а 8 | а 9 | а 10 | а 11 | а 12 | а 13 | а 14 | |
| а 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| а 2 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| а 3 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| а 4 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| а 5 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| а 6 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| а 7 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| а 8 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| а 9 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| а 10 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| а 11 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| а 12 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| а 13 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| а 14 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| а 1 | а 2 | а 3 | а 4 | а 5 | а 6 | а 7 | а 8 | а 9 | а 10 | а 11 | а 12 | а 13 | а 14 | |
| а 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| а 2 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| а 3 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| а 4 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| а 5 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| а 6 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| а 7 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| а 8 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| а 9 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| а 10 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| а 11 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| а 12 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| а 13 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| а 14 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| а 1 | а 2 | а 3 | а 4 | а 5 | а 6 | а 7 | а 8 | а 9 | а 10 | а 11 | а 12 | а 13 | а 14 | |
| x 1 | 1 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | -1 | 0 | 0 | 0 | 0 | 0 |
| x 2 | -1 | 0 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| x 3 | 0 | 0 | -1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 |
| x 4 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 1 | 0 | 0 | 0 | -1 | 0 | 0 |
| x 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 1 | 0 | 0 | -1 | 0 |
| x 6 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | -1 |
| x 7 | 0 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 1 |
| а 1 | а 2 | а 3 | а 4 | а 5 | а 6 | а 7 | а 8 | а 9 | а 10 | а 11 | а 12 | а 13 | а 14 | |
| x 1 | 1 | 0 | 0 | 1 | 0 | 0 | -1 | 0 | -1 | 0 | 0 | 0 | 0 | 0 |
| x 2 | 0 | -1 | 1 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| x 3 | -1 | 1 | 0 | 0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| x 4 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | -1 | 1 | 0 |
| x 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | -1 | 1 |
| x 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | -1 | 0 | 1 | 0 | -1 |
| x 7 | 0 | 0 | 0 | 0 | 1 | -1 | 0 | 0 | 0 | 1 | -1 | 0 | 0 | 0 |
S 2
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |
| x 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |
| x 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |
| x 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |
| x 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x 7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Q 1 Q 2
3. Знайти і побудувати об'єднання, перетин, кільцеву суму заданих графів.
Об'єднання графів
SHAPE \ * MERGEFORMAT
X 1 |
X 3 |
X 4 |
X 6 |
X 7 |
X 5 |
X 2 |
G 3 (X 3, A 3) = G 1 (X 1, A 1) YG 2 (X 2, A 2); X 3 = X 1 YX 2, A 3 = A 1 YA 2
Перетин графів
SHAPE \ * MERGEFORMAT
X 1 |
X 3 |
X 4 |
X 6 |
X 7 |
X 5 |
X 2 |
G 3 (X 3, A 3) = G 1 (X 1, A 1) ∩ G 2 (X 2, A 2); X 3 = X 1 ∩ X 2, A 3 = A 1 ∩ A 2
Кільцева сума графів
SHAPE \ * MERGEFORMAT
X 1 |
X 3 |
X 4 |
X 6 |
X 7 |
X 5 |
X 2 |
G 3 (X 3, A 3) = G 1 (X 1, A 1)
4. Знайти і побудувати композицію графів
| G 1 (Х) | G 2 (Х) | G 1 (G 2 (Х)) | G 2 (G 1 (Х)) | |
| x 1 | (X 1, x 2), (x 1, x 7) | (X 1, x 2), (x 1, x 3) | (X 1, x 3), (x 1, x 6), (X 1, x 2), (x 1, x 4), | (X 1, x 4), (x 1, x 5), (X 1, x 3), (x 1, x 6), |
| x 2 | (X 2, x 3), (X 2, x 6) | (X 2, x 4), (X 2, x 5) | (X 2, x 1), (x 2, x 5), (X 2, x 7), | (X 2, x 2), (x 2, x 7), (X 2, x 1), (x 2, x 4), |
| x 3 | (X 3, x 2), (X 3, x 4) | (X 3, x 2), (X 3, x 7) | (X 3, x 3), (x 3, x 6), (X 3, x 5), | (X 3, x 4), (x 3, x 5), (X 3, x 1), |
| x 4 | (X 4, x 1), (x 4, x 5) | (X 4, x 1), (x 4, x 5) | (X 4, x 2), (x 4, x 7), (X 4, x 1), | (X 4, x 2), (x 4, x 3), (X 4, x 6), (x 4, x 7), |
| x 5 | (X 5, x 1), (x 5, x 7) | (X 5, x 6), (x 5, x 7) | (X 5, x 3), (x 5, x 4), (X 5, x 5), (x 5, x 6), | (X 5, x 2), (x 5, x 3), (X 5, x 6), |
| x 6 | (X 6, x 3), (X 6, x 4) | (X 6, x 1), (X 6, x 4) | (X 6, x 2), (x 6, x 7), (X 6, x 1), (x 6, x 5), | (X 6, x 2), (x 6, x 7), (X 6, x 1), (x 6, x 5), |
| x 7 | (X 7, x 5), (x 7, x 6) | (X 7, x 3), (x 7, x 6) | (X 7, x 2), (x 7, x 4), (X 7, x 3), | (X 7, x 6), (x 7, x 7), (X 7, x 1), (x 7, x 4), |
X 1 |
X 3 |
X 4 |
X 6 |
X 7 |
X 5 |
X 2 |
SHAPE \ * MERGEFORMAT
X 1 |
X 3 |
X 4 |
X 7 |
X 5 |
X 2 |
X 6 |
G 2 (G 1 (Х))
5. Для кожного графа знайти і побудувати остовних підграф, довільний підграф, породжений пiдграф.
Остовних підграфи
SHAPE \ * MERGEFORMAT
X 1 |
X 3 |
X 4 |
X 6 |
X 7 |
X 5 |
a 1 |
a 3 |
a 6 |
a 9 |
a 12 |
a 13 |
a 14 |
X 2 |
G '1 (X 1, A 1)
SHAPE \ * MERGEFORMAT
X 3 |
X 4 |
X 5 |
X 6 |
X 7 |
X 1 |
a 1 |
a 2 |
a 3 |
a 9 |
a 10 |
a 14 |
a 13 |
X 2 |
G '2 (X 2, A 2)
Довільні підграфи
SHAPE \ * MERGEFORMAT
X 1 |
X 3 |
X 4 |
X 6 |
a 1 |
a 3 |
a 6 |
a 12 |
G 1''(X 1'', A 1'')
SHAPE \ * MERGEFORMAT
X 3 |
X 4 |
X 1 |
a 1 |
a 2 |
a 3 |
|
Породжені підграфи
|
X 1 |
X 7 |
X 5 |
a 2 |
a 9 |
a 13 |
a 1 |
a 10 |
X 6 |
a 6 |
a 9 |
G 1P (X 1P, A 1P) G 2P (X 2P, A 2P)
6. Визначити локальні ступеня вершин графа, перевірити чи існує в даному графі ейлерова ланцюг, Ейлером цикл.
Локальні ступеня графа G 1
Локальні ступеня графа G 2
Ейлерова ланцюг існує у двох графах, тому що всі локальні ступеня графів парні.
Ейлеров цикл існує у двох графах, тому що всі локальні ступеня графів парні.
7. Визначити хроматичні і Цикломатичне числа даних графів.
SHAPE \ * MERGEFORMAT
2 |
1 |
2 |
1 |
3 |
4 |
3 |
X 1 |
X 3 |
X 6 |
X 7 |
X 5 |
X 2 |
X 4 |
Хроматичне число γ для графа G 1 = 4
SHAPE \ * MERGEFORMAT
3 |
1 |
2 |
4 |
1 |
2 |
3 |
X 3 |
X 6 |
X 7 |
X 1 |
X 2 |
X 4 |
X 5 |
Хроматичне число γ для графа G 2 = 4
Цикломатичне числа графів
V (G 1) = m-n + r, де m - число ребер (дуг);
n - число вершин;
r - число компонент зв'язності.
V (G 1) = 14-7 +1 = 8;
V (G 2) = 14-7 +1 = 8;
8. Знайти всі бази графа.
Бази графа G 1
B 1 = {x 1}
B 2 = {x 2}
B 3 = {x 3}
B 4 = {x 4}
B 5 = {x 5}
B 6 = {x 6}
B 7 = {x 7}
Бази графа G 2
B 1 = {x 1}
B 2 = {x 2}
B 3 = {x 3}
B 4 = {x 4}
B 5 = {x 5}
B 6 = {x 6}
B 7 = {x 7}
B 1 = {x 1}
B 2 = {x 2}
B 3 = {x 3}
B 4 = {x 4}
B 5 = {x 5}
B 6 = {x 6}
B 7 = {x 7}
Бази графа G 2
B 1 = {x 1}
B 2 = {x 2}
B 3 = {x 3}
B 4 = {x 4}
B 5 = {x 5}
B 6 = {x 6}
B 7 = {x 7}
9. Визначити в кожному графі сильні компоненти зв'язності, побудувати конденсацію графа.
Сильні компоненти зв'язності G 1
СК = {x 1, x 2, x 3, x 4, x 5, x 6, x 7}
Сильні компоненти зв'язності G 2
СК = {x 1, x 2, x 3, x 4, x 5, x 6, x 7}
SHAPE \ * MERGEFORMAT
Конденсація графа G 1 Конденсація графа G 2
Сильні компоненти зв'язності G 1
СК = {x 1, x 2, x 3, x 4, x 5, x 6, x 7}
Сильні компоненти зв'язності G 2
СК = {x 1, x 2, x 3, x 4, x 5, x 6, x 7}
SHAPE \ * MERGEFORMAT
Z 1 |
Z 1 |
Конденсація графа G 1 Конденсація графа G 2