Программирование, группа 6113

Задание 7. Индивидуальное задание на графы

1. Гуров Геннадий
   Проверить, содержит ли данный связный неориентированный граф хотя бы одну точку сочленения, т.е. вершину, при удалении которой из графа в графе увеличивается количество компонент связности.
2. Кондрашкин Евгений
   Даны неориентированный граф и число k. Найти все вершины графа, расстояние от которых до первой вершины графа равно k.
3. Леуцкий Евгений
   Для данного связного неориентированного графа найти диаметр графа, т.е.
   

   max (i,j) н E  D(i, j)

   (D(i,j) — длина кратчайшего пути между вершинами i и j).
4. Мирзагитов Азат
   В данном связном неориентированном графе найти длины кратчайших путей между всеми парами вершин.
5. Ракшаева Екатерина
   Даны неориентированный граф и число k. Выяснить, есть ли в данном графе вершина, расстояние от которой до каждой вершины не превышает k.
6. Сороковой Алексей
   Дан связный неориентированный взвешенный граф (т.е. каждое ребро графа имеет неотрицательный вес, который можно условно считать расстоянием между соответствующими вершинами). Найти вершину графа, сумма длин кратчайших путей от которой до всех остальных вершин графа минимальна.
7. Уланова Евгения
   Найти все вершины данного неориентированного графа, недостижимые из первой вершины.
8. Шипилов Владислав
   Подсчитать количество компонент связности в данном неориентированном графе.
9. Шкарлет Валентина
   Правильной раскраской вершин графа в k цветов называется такое отображение c: V ╝ {1 ╪k}, что
   

   c(i) ╧ c(j)   для любого ребра   (i, j) н E .

   Выяснить, можно ли раскрасить данный неориентированный граф в 2 цвета, и вывести эту раскраску, если можно.
10. Щербаков Виктор
    Дан связный неориентированный взвешенный граф (т.е. каждое ребро графа имеет неотрицательный вес, который можно условно считать расстоянием между соответствующими вершинами). Найти кратчайшие пути от первой вершины до всех остальных вершин графа.