Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Графы >> Номер 11

[Назад]    [Содержание ]    [Вперед]

  


Номер 11


  Условие: Номер 11


Задача 11. На олимпиаду прибыло N человек. Некоторые из них знакомы между собой. Можно ли опосредованно перезнакомить их всех между собой? (Незнакомые люди могут познакомиться только через общего знакомого).

  Решение задачи: Номер 11


Решение задачи 11. Для решения задачи достаточно определить, является ли связным граф, определяемый матрицей смежности, элементы которой а[i,j] равны 1, если люди с номерами i и j знакомы и равны 0 иначе. Граф называется связным, если существует путь между любыми парами его вершин. Понятно, что путь между вершинами i и j в таком графе и определяет возможную последовательность знакомств, позволяющих познакомить людей с номерами i и j. Для определения связности графа можно воспользоваться методом поиска в ширину, который состоит в следующем. На начальном этапе в очередь помещается некоторая начальная вершина, например вершина с номером 1. На каждой из следующих итераций (пока очередь не пуста) выполняются следующие действия: - извлекается вершина из очереди; - определяются вершины, ей смежные и которые в очереди еще не были, и помещаются в очередь. Если в результате таких действий все вершины побывали в очереди (а для этого удобнее подсчитывать количество вершин, там побывавших), то граф связен, иначе не связен. Для маркировки вершин, побывавших в очереди, можно использовать массив размера N с элементами 0 и 1.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017