WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 |

Критерий планарности Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных графам K5 или K3,3.

Операция стягивания ребра (a,b) в графе G (V, E) состоит в отождествлении (слиянии) смежных вершин a и b. Граф G называется стягиваемым к графу G, если G получается из G в результате некоторой последовательности стягиваний ребер.

Критерий планарности Вагнера. Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых к графам K5 или K3,3.

4.1. Построить граф пересечений граней куба. Написать матрицу смежности полученного графа.

4.2. В графе n вершин и m ребер. Сколько у него 1) остовных подграфов;

2) порожденных подграфов 4.3. Определить число графов с n вершинами, в которых допускаются ребра следующих типов:

1) неориентированные и петли;

2) ориентированные и петли;

3) ориентированные, но не петли.

4.4. Определить число ориентированных графов с n вершинами, в которых каждая пара различных вершин соединена:

1) не более чем одним ребром;

2) точно одним ребром.

4.5. Выяснить, существуют ли графы с набором степеней:

1) (0,2,2,3,3); 2) (2,2,2,3,3);

3) (2,2,3,3,3); 4) (0,1,2,3,4).

4.6. Определить число ребер в каждом из графов Kn, K, Qn.

p,q 4.7. Граф перестановок порядка k строится следующим образом. Его вершины соответствуют всевозможным перестановкам элементов 1, 2,..., k. Две вершины смежны тогда и только тогда, когда одна из соответствующих перестановок может быть получена из другой перестановки одной транспозицией. Определите число ребер в этом графе.

4.8. При каких n существуют графы с n вершинами, каждая из которых имеет степень 3 степень 4 4.9. Вершина степени 0 называется изолированной. Определите число графов с n вершинами, в которых 1) данные k вершин являются изолированными;

2) нет изолированных вершин (примените метод включения и исключения).

4.10. Графы, изображенные на рис. 2, разбить на классы попарно неизоморфных графов.

1 2 3 7 9 10 13 14 Рис. 2. К задаче 4.4.11. Перечислить все попарно неизоморфные графы:

1) с 4 вершинами;

2) с 6 вершинами и 3 ребрами;

3) с 6 вершинами и 13 ребрами.

4.12. Перечислите все попарно неизоморфные ориентированные графы без петель с тремя вершинами и тремя ребрами.

4.13. Графы, изображенные на рис. 3, разбить на классы попарно неизоморфных графов.

1 2 3 4 6 7 8 Рис. 3. К задаче 4.4.14. Графы, изображенные на рис. 4, разбить на классы попарно неизоморфных графов.

1 2 Рис. 4. К задаче 4.4.15. Графы, изображенные на рис. 5, разбить на классы попарно неизоморфных графов.

1 2 3 4 6 7 8 9 Рис. 5. К задачам 4.15 и 4.4.16. Графы, изображенные на рис. 6, разбить на классы попарно неизоморфных графов.

1 2 3 4 7 8 9 Рис. 6. К задаче 4.4.17. Граф G называется самодополнительным, если G G. Найти все самодополнительные графы с числом вершин, не превосходящим 6.

4.18. Определите число простых путей и простых циклов длины k в графах Kn и K.

p,q 4.19. В графе Qn найдите число простых путей длины n, соединяющих вершины (0,0,...,0) и (1,1,...,1).

4.20. Доказать, что в каждом графе с не менее чем двумя вершинами найдутся две вершины с одинаковыми степенями.

4.21. Найти радиус и диаметр каждого из графов Pn, Cn, Qn, K.

p,q 4.22. Найти радиус, диаметр, центр графа, заданного матрицей смежности:

0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 0 1) ; 2) ; 3).

0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 Определить, является ли граф эйлеровым. В случае положительного ответа построить в нем эйлеров цикл.

4.23. Построить граф, центр которого:

1) состоит ровно из одной вершины;

2) состоит из двух вершин;

3) состоит из трех вершин и не совпадает с множеством всех вершин;

4) совпадает с множеством всех вершин.

4.24. Найти радиус, диаметр, центр графа, заданного матрицей смежности:

0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1) ; 2) ; 3).

0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 Определить, является ли граф гамильтоновым. В случае положительного ответа построить в нем гамильтонов цикл.

4.25. Какое наименьшее число ребер может быть в связном графе с n вершинами 4.26. Могут ли графы G и G оба быть несвязными 4.27. Найти граф G с минимальным числом вершин n 1, такой, что G и G оба связны.

4.28. Какое наибольшее число ребер может быть в несвязном графе с n вершинами 4.29. При каких p и q в графе K есть эйлеров цикл Эйлеров путь Гамильp,q тонов цикл При каких n в графе Qn есть эйлеров цикл 4.30. Доказать, что в графе Qn при любом n 2 имеется гамильтонов цикл.

4.31. Найти граф с шестью вершинами, который имеет эйлеров цикл, но не имеет гамильтонова цикла.

4.32. Найти граф с шестью вершинами, который имеет гамильтонов цикл, но не имеет эйлерова цикла.

4.33. Какие из графов, изображенных на рис. 5, являются двудольными 4.34. Каково наибольшее число ребер в двудольном графе с n вершинами 4.35. Двудольный граф имеет k компонент связности. Каким числом способов его можно разбить на две доли 4.36. Перечислить все попарно неизоморфные деревья с числом вершин, не превышающим 6.



4.37. Найти два неизоморфных дерева с одинаковыми наборами степеней.

4.38. Сколько ребер в лесе с n вершинами и k компонентами связности 4.39. Сколько ребер в связном графе с n вершинами, если в нем имеется единственный цикл 4.40. В дереве с n вершинами степень каждой вершины равна 1 или k. Сколько листьев в таком дереве 4.41. Найти число корневых деревьев с множеством вершин (1,..., n).

4.42. Построить код Прюфера для деревьев, изображенных на рис.7.

7 3) 1) 2) 7 1 5 6 4 6 3 1 5 3 8 9 9 4 5) 6) 3 2k+ 4) 3 2k+ k+1 k+2 2k-2 2k- 2k-3 2k-1 2k 5 1 2 k- 3 2k+1 1 2k+ 1 k Рис. 7. К задаче 4.4.43. По заданному коду Прюфера p(T ) восстановить дерево. Найти центральные вершины восстановленного дерева.

1) P(T ) (4,1,6,2,2,2,7) ;

2) P(T ) (4,2,3, 4,2,3,1,1) ;

3) P(T ) (5,2,5,3,5,4,9,6) ;

4) P(T ) (2,2,...,2) ;

n5) P(T ) (1,2,..., n 2) ;

6) P(T ) (3,3,4,5,..., n 2, n 2).

4.44. Найти все графы, которые являются деревьями вместе со своими дополнениями.

4.45. Какие из графов, изображенных на рис. 8, планарны 1 2 3 4 6 7 8 9 Рис. 8. К задаче 4.4.46. Какое наименьшее количество ребер нужно удалить из графа G, чтобы получить планарный граф, если:

1) G = K6 ;

2) G =Q4 ;

3) G - граф Петерсена (рис. 9) Рис. 9. Граф Петерсена 4.47. Построить граф с 6 вершинами и 12 ребрами, который содержит одновременно подграфы, гомеоморфные K5 и K3,3.

4.48. Выяснить, существует ли планарный граф, у которого:

1) 7 вершин и 16 ребер;

2) 8 вершин и 17 ребер.

4.49. Какое наибольшее число граней может быть у плоского пятивершинного графа, не имеющего петель и кратных ребер Изобразить этот граф.

4.50. При каких n граф Qn планарен 4.51. Объединением графов G1 (V1, E1 ) и G2 (V2, E2 ) называется граф G (V1 V2, E1 E2 ). Можно ли граф K7 разложить в объединение двух планарных подграфов 4.52. Перечислите все графы с указанными свойствами и значениями параметров (в скобках указано число искомых графов):

1) 6 вершин, 5 ребер (15);

2) 7 вершин, 4 ребра (10);

3) связные, 6 вершин, 6 ребер (13);

4) связные, 5 ребер (12);

5) две компоненты связности, 4 ребра (9);

6) без изолированных вершин, 4 ребра (11);

7) набор степеней (2,2,2,3,3,4) (4);

8) набор степеней (2,2,3,3,3,3) (4);

9) деревья, 7 вершин (11);

10) деревья, набор степеней (1,1,1,1,2,2,2,3,3) (9);

11) деревья, набор степеней (1,1,1,1,1,2,2,3,4) (8);

12) леса, 5 вершин (10);

13) деревья, степени не более 3, 8 вершин (11);

14) графы с единственным циклом, 5 вершин (9);

15) графы с единственным циклом, 6 вершин, 5 ребер (8);

16) связные, не имеющие циклов длины 3, 5 вершин (6);

17) имеющие эйлеров цикл, 6 вершин (8);

18) имеющие эйлеров цикл, 7 вершин, 9 ребер (3);

19) имеющие гамильтонов цикл, 5 вершин (8);

20) имеющие гамильтонов цикл, 6 вершин, 8 ребер (6);

21) имеющие цикл длины 6, 5 вершин (6);

22) непланарные, 6 вершин, 11 ребер (4);

23) двудольные, 5 вершин (13);

24) двудольные, 6 вершин, 6 ребер (6);

25) ориентированные, без петель, 3 вершины (16);

26) ориентированные, без петель, 4 вершины, 3 ребра (13).

5. Контрольные задания 5.1. Контрольная работа по алгебре множеств Задача 1. Доказать или опровергнуть утверждения:

1. A BCBC A B B.

2. A B A CB C.

3. A BCBC ABC ABC.

4. A B ABA C AC ABC.

5. AB ABC C A.

6. A ABC A BCBC ABC.

7. A BC A BC ABC.

8. AB U C U A BA C.

9. A BC AC B A BC AC B.

10. A BC A A B ABA C.

11. A BС A.

A BС BС 12. ABC ABA CA B C.

C 13. A B C A B C A A.

14. A BС A BС A BС A BС.

15. AС ABС.

BС BС 16. A BC U A B C.

17. AC BB AC C C.

18. AC BC AC CBC C.

19. AC BB ABC ABC.

20. AC ABC AC BCBC ABC.

21. С B C A B A.

22. C B CBA C CA C BA.

23. B ABC B ACAC ABC.

24. С ABC С BCBA ABC.

25. CB U A U C BC A.

26. С A B C С B СB С A.

27. A B ( AC ABC) AC B B.

28. A BС A BС A BС ABС.

29. C BA U C B A.

30. AB CC ACB ABC.

Задача 2. Задано универсальное множество U 1,2,3,4,5,6,7 и в нем подмножества A x x 4, B 2,4,5,6, C 1,3,5,6, D {x | x – простое1}, E 1, 2,6,7. Найдите множества:

AC 1. A B D E; С AE D; 2 2E ; C ABD.

AC 2. С AB; C D E E D; 2DC 2B C ; B.

A D A 3. С A B E; AC AB D; 2C D 2 ; ( A B).

A AD 4. B E; CE D A B; 2 2B ; B C.

5. A E D; С B BC A ; 2B C 2C D ; (B E)BD.

A 6. E AC; A B CC D; 2 2B C ; B EAC.

7. С D E A; BC BC E; 2B D 2C D ; ( A E)B.

A B A B 8. B С D E; A C A B; 2 2C ; (C D).

9. B A DC; D AE C; 2D E 2C ; ( A B)D.

A B A E 10. D BC; C E D A B; 2 2D C ; E.

A D 11. D B E; B D CB D; 2D E 2 ; (BC)E.

C A D 12. СD A; A B B D; 2 2E ; CE D.

13. AC E; DC AC B ; 2C E 2B E ; ( A B)C.

D C AC 14. D B E; B C A D E; 2D 2 ; B.

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

15. DE A; C E AD E); 2E 2C D ; (B D)C.

C B A B 16. D С B E; DE AC; 2 2C ; D.

AE 17. AB AD; B D C; 2BC 2C E ; AD.





AC 18. A E BD; BD B D AE; 2 2B D ; ACD.

AC 19. E B D AC; AC E BD; 2B 2 ; A DAC.

AB A E ABC 20. BD A BC; AC BD BD; 2 2 ; AC.

AC 21. С AB ; СD E E D; 2D C 2B C ; B.

A B 22. A E; CE D A B; 2BD 2 ; ( A C ).

AD 23. B AC; A B C C D; 2 2B C ; B EAC.

A B A B 24. A С D E; AC A B; 2 2C ; (C D) A B A B 25. BС D E; A C A B ; 2 2C ; (C D).

A B A E 26. A BC; C E D A B; 2 2DC ; E.

AC AC 27. EBD AC; AC E B D; 2B 2 ; AD.

D C 28. A B E; B C A D E; 2D 2AC ; B.

C B A B 29. A С B E; DE AC; 2 2CD ; A.

D AC 30. AE BD; BABD AD; 2 2B D ; BC.

Задача 3. Упростить условия:

A B C;

A B C;

B C D D;

AD B C;

1. 2.

AB C D; D C;

AC C B D. AD B C D.

BC A D; A B C;

AB C D;

B D A;

3. 4.

BD AC A C; C D A B;

B A C. AB D.

A B C; A C D;

5. D A B C; 6. A B C D;

BC A D. AD B C.

X Y Z ;

B C D;

Y Z W W ;

A B C;

7.

8.

Z W ;

D C;

X W Y Z W.

AD B C D.

X Y Z ; X Y Z ;

XW Y Z; Y Z W ;

9.

10.

XY Z W ;

W Z;

XZ Z Y W.

X W Y Z W.

CD A B; C A D;

BC A D;

D B C;

11. 12.

AC B D; A B C D;

C B D. CD B.

A B A C D;

W X Y ;

B C D;

X Y Z;

14.

13.

C A D A;

ZW X Y Z;

A D.

Y Z.

A B D;

A C D;

15. AC B D;

16. A B C D;

AC D B. С D B.

Z X Y ;

A C D;

Y X W ;

D B C;

18.

17.

X W ;

BD C;

ZW XYW.

C D AB.

XY Z W ;

AD B C;

Y X Z; BD A C;

20.

19.

CD A B;

X W Y Z;

D B C.

Y W X Z X Z.

B A C;

A B C;

A D B;

B C D D;

22.

21.

C D A B;

D C;

AB D.

AD B C D.

C A D; D C A;

23. C B A D; 24. D B C A;

С A B.

CD B A.

A C D;

Y X Z;

D B A;

X Z W ;

26.

25.

C B A D;

W Z;

AD B.

Y W X Z W.

A C A B D;

C C D;

C B D;

A B C;

27.

28.

B A D A;

D B;

A D.

AD B C D.

X Z Y ;

BD A C;

Y Z W ; AD B C;

29. 30.

CD A B;

Z W ;

XW ZYW. D A C.

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

1. A B X AB.

2. A B X AB A BX.

3. A BX X.

4. A BX B U.

5. A X B A B.

6. A BX A B.

7. A X B AX.

8. BX A BX A.

9. A X X AB.

10. B X X B A.

11. A X B B X.

12. AX B B X.

13. BX A B X.

14. A X BX A.

15. X A B X A.

16. AX X A B.

17. A B X A X.

18. B AX B X.

19. A B X A B.

20. A X B A B.

21. A BX AB A B X.

22. B AX A U.

23. B AX A B.

24. ABX AX B.

25. BX A BX A.

26. A X X A B.

27. BX A A X.

28. ВX X B A.

29. A BX A X.

30. B X A BA.

Задача 5. Решить систему уравнений. Найти необходимые и достаточные условия, при которых система имеет решение. Оценить число решений системы уравнений.

A X AC, A X C, B 1. X B C, 2. X C, B C X A B.

BX AX C.

X B B C, AX B, 3. X A A C, 4. X C, B C X A B.

X C B C.

A X B, AX B X C, 6.

5.

B X С.

BX A X C.

A B X A, A X B X C X, 8.

7.

A B X С.

B X C A X.

A X B X, A X X B, 10.

9.

A X C X.

A X C.

A X B, A X B, 11. 12.

B X C. BX C X AС.

A B X С, A X C, 13. 14.

A B X С.

B X A.

A X X C, B X A X, 15. 16.

A X B. A X C X.

A X B, AX С X B, 18.

17.

B X С.

BX C X A.

С X X B, A X C X, 19.

20.

A X B.

A X B X.

С X A, AX C, 21. X A, 22. X A, B B BX C X A. C X A B.

B X A, C B X C, 24.

23.

A C B X.

A X С.

C X B X, С X B, 25.

26.

AC BX A X.

CX A X.

B X C, A X B X, 27. 28.

B A X. B X C X.

A B X, C X A X, 29.

30.

A X С.

C X B X.

Задача 6. Равносильны ли системы условий:

A B C;

C B A D; A B;

1.

C A D B; B C B D.

AC B;

W Z ;

Y X ;

Y Z W ;

2.

X Z W.

X Y Z;

XW YZW ;

A B D; A B;

3. AC D; A C;

C A B;

D B.

A D B C D;

C D;

C A D;

4.

B A B C.

CD B;

A B C;

Y ZW ;

X Z Y Z ;

XW YZW ;

5. Y ZW ;

X Y Z ;

W Z.

Z W ;

A B D;

A B;

AC D;

6. A C;

C A B;

D.

B D;

A C;

AD BCD;

7. A B C D; A B;

B D;

C D.

Y ZW ;

X Y ;

XW YZW ;

8. X Z;

X Y Z;

W.

W Z ;

A B D;

A B;

AC D;

9. A C;

C A B;

A D.

B D;

X Z Y W ;

X W ;

10. XW YZ YW ;

Y Z.

X W ;

B C A;

A B C D; B C;

11.

Pages:     | 1 | 2 || 4 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.