Задания для самостоятельной работы к разд.3.1

1. Определить число рёбер в полном графе порядка n. Нарисовать примеры полных графов порядка 2, 3, 4, 5.

2. Определить число рёбер в покрывающем дереве графа порядка n.

3. Постройте алгоритмы для преобразования друг в друга всех пар следующих представлений графа:

а) матрица смежности;

б) список рёбер;

в) список смежности;

г) матрица инцинденций.

Анализ графов на связность

На практике часто необходимо знать, связен ли данный граф. Если граф не связен, то может потребоваться найти все его компоненты. Приведём пример практической задачи, сводящейся к вопросу о связности графа.

Задача 3. В небольшой деревушке некоторые из жителей имеют каждодневные встречи друг с другом. Может ли в этой деревне распространиться какой-либо слух?

Чтобы ответить на этот вопрос, поставим в соответствие каждому жителю деревни вершину графа. Соединим две вершины ребром, если соответствующие жители ежедневно общаются друг с другом. При условии связности полученного таким образом графа на поставленный в задаче вопрос можно ответить положительно.

В данном разделе будут рассмотрены алгоритмы для решения таких и других подобных задач.