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

Написать кр. Скидывать по номеру два. Контрольная до 15: 00, но лучше решить всё до 14:30.

Если знаете как решить только часть задач, пишите, пожалуйста. Можем договориться договоримся об одной или нескольких задачах.

1)     В ориентированном графе, найти сильные и слабые компоненты, множества баз и антибаз.

2)     Для неориентированного графа с помощью эврестической процедуры раскрашивания найти раскраску и хроматическое число.

3)     Для ориентированного графа найти максимально независимые и минимально доминирующие множества методом Ману.

4)     В бесконтурном орграфе определить функцию Гранди.

6)     В графе произвести поиск в ширину и глубину.

7)     Для взвешенного неориентированного графа найти кратчайший остов и его длину.

8)     В ориентированном графе найти путь с минимальным числом дуг из правой вершины в левую.

9)     Для взвешенного ориентированного найти кратчайший путь из S в t(вершины).

10)     Осуществить топологическую сортировку вершин в бес контурном графе

11)     Во взвешенном ориентированном графе найти критический путь из S в t. S-источник t – сток