Тема 21. Основные понятия и определения теории графов.
№1.2. По заданным полу степеням вершин постройте, если это возможно, ориентированный граф:
4) Р+(хi)=1, P_(xi)=1, i=1,…,4;
5) P+(x1)=P+(x2)=P_(x2)=P_(x3)=1,
P+(x3)=P_(x1)=2;
6) P+(xi)=i, P_(xi)=6-i, i=1,…,5.
№1.3. По заданным степеням вершин постройте, если это возможно, неориентированный граф:
4) P(xi)=3, i= 1,…,4;
5) P(xi)=i, i=1,…,5;
6) P (x1)=1, P (x2)=2, P (x3)=7.
Тема 22. Эйлеровы и гамильтоновы графы. Теорема Эйлера.
№1.4. Определите, являются ли следующие графы эйлеровыми (гамильтоновыми). Если да, то укажите эйлеров (гамильтонов) цикл.
1. х2 х3 2. х2 х3
х6
х5 х6 х4
х1 х4 х1 х5
х3 х4 х5
4.
3. х1 х9 х10 х6 х2 х3
х1 х8 х1 х7 х8 х4
х6 х5
`
№1.5. Укажите, если он существует, изомореризм следующих графов:
1. х2 х3 у2 у3
и
х1 х4
у1 у4
2. х2 х3 у2 у3
 |  |
и
 |  |
х1 х4 у1 у4
3. х2
у2 у3
и
х4
х1 х3 у1 у4
х3 у2 у3
4.
х2 х4
и
у1 у4
х1 х5
у5
№1.6. Перечислите все неизоморфные между собой подграфы данного графа:
1. 2.
Литература:[2,3,4,7,16,17,19,21,23,24,25]
Учебно-методическая литература:[2]
Тема 23. Планарные или плоские графы. Теорема Куратовского.
№1.7. Являются ли следующие графы плоскими:
1. 2. х3 х4 х5
х6
х2
х7
х1 х8
№1.8. В графе 4) из №1.4.:
3) слейте вершины: а) х2 и х4, б) х2 и х5;
4) стяните ребро: а) (х8х4), б) (х7х5).
Литература:[2,3,4,7,16,17,19,21,23,24,25]
Учебно-методическая литература:[2]
Дата добавления: 2015-09-12; просмотров: 26 | Поможем написать вашу работу | Нарушение авторских прав |