53. Контрольное задание №2.1

1. Задайте графическим и матричным способом ориентированный, неориентированный, смешанный граф. 2. Изобразите граф G = {V, E}, где a. V= {v1,v2,v3,v4,v5}, E={(v1,v5),(v1,v3),(v3,v5),(v3,v4),(v1,v4)} b. V= {v1,v2,v3,v4,v5}, E={(v1,v2),(v1,v5),(v2,v5),(v3,v4),(v5,v4)} c. V= {v1,v2,v3,v4,v5}, E={(v5,v2),(v1,v3),(v4,v5),(v5,v4),(v3,v4)} d. V= {v1,v2,v3,v4,v5}, E={(v4,v2),(v1,v3),(v1,v5),(v3,v1),(v5,v4)} e. V= {v1,v2,v3,v4,v5}, E={(v5,v2),(v1,v3),(v4,v1),(v3,v4),(v1,v4)} 3. Постройте матрицу для изображенного в предыдущем задании графа. 4. Постройте полный граф с 4 вершинами. 5. Постройте граф, изоморфный графу из первого задания. 6. Составьте словесный алгоритм определения маршрута в графе. 7. Составьте структурную схему алгоритма определения связности произвольного неориентированного графа. 8. Выполнить пересечение графов G1 = {V1,E1}, где V1 = {v1,v2,v3,v4,v5} E1= {(v1,v3),(v2,v4),(v3,v5)} и G2 = {V2,E2}, где V2 = {v6,v7,v8,v3,v5} E1= {( v3,v5),(v6,v8),(v3,v7)} 9. Доказать или опровергнуть:

A. объединение любых двух различных цепей, соединяющих две вершины, содержат простой цикл;

B. объединение любых двух различных простых цепей, соединяющих две вершины, содержит простой цикл.

10. Если d(u, v) = m в графе G, то чему равно d(u, v) в графе Gn?

11. Найти наибольшее число ребер в графе с p вершинами, не имеющем четных простых циклов.

12. Докажите, что если в графе G существуют пути между вершинами a и b, а также между b и c, то существует путь между a и c.

13. Докажите, что замкнутая цепь, все вершины которой имеют степень два, является циклом.

14. Докажите, что граф Gявляется связным тогда и только тогда, когда для каждого разбиения (V1, V2) множества Vс непустыми V1и V2 существует ребро в G, соединяющее вершину из V1с вершиной изV2.

15. Покажите, что простой граф G, имеющий по крайней мере две вершины, содержит две вершины одинаковой степени.

16. Существует ли два различных графа с одной и той же матрицей циклов? Покажите.

< Предыдущая		Следующая >