Первый уровень

[851] Найдите вершину графа, из которой выходит наибольшее число ребер.

[852] Найдите вершину графа, у которой наибольшая сумма длин ребер, выходящих из этой вершины.

[853] Упорядочите ребра графа по возрастанию цен ребер. В ре­зультате укажите цену и через тире - номер вершин, которые содер­жат данное ребро.

[854] Упорядочите вершины графа по возрастанию количества ребер, выходящих из этой вершины. Результат дайте в следующем виде: номер вершины и рядом (в круглых скобках) число, выра­жающее количество выходящих из этой вершины ребер.

Второй уровень

[855] Найдите три вершины графа такие, чтобы сумма цен связы­вающих их ребер была максимальна.

[856] Имеется семь городов, соединенных некоторой сетью до­рог. В каком городе необходимо провести конференцию так, чтобы суммарный путь всех делегатов, по одному из каждого города, был минимален.

[857] Удалите одно ребро графа таким образом, чтобы получи­лись два не связных между собой графа.

Третий уровень

[858] Найдите кратчайший путь от данного источника графа до любой конечной точки, используя алгоритм Форда-Беллмана.

[859] Найдите кратчайшее расстояние от вершины S графа до вершины Р , если при этом нужно пройти через вершину Q.

[860] В данном графе найдите кратчайший путь от вершины А до вершины В, если заходить в вершину С нельзя.

[861] Дан граф. Найдите кратчайшее расстояние от вершины NA до вершины KON , если при этом нужно пройти через вершины Р и Q.

[862] Пусть сумма кратчайших расстояний от источника S до всех остальных вершин графа будет равна SUM. Определите вершину, которая, будучи источником, имеет наименьшее значение SUM.

[863] Несколько городов соединены сетью дорог, заданной в виде графа. В каждом городе машина может дозаправиться некото­рым, постоянным для данного города, объемом горючего. Единица заправки соответствует единице расстояния. Найдите путь из ука­занного города, позволяющий обойти наибольшее число городов, если известен объем заправка в каждом городе.

[864] "Селения". Имеется k селений. Если в селении i располо­жить пункт скорой помощи, то поездка в селение j займет время А(i ,j )+A(i ,j) где (1<=i , j<=k). Найдите номер селения i, от которого поездка в самое удаленное селение (по времени) заняла бы мини­мальное время. Массив A(k, k) задан. В нем все A(i ,J)>0, и элемент A(i ,J) может быть не равен элементу A(J , i).

[865] Пусть n - количество вершин графа. Найдите самый нужный путь от заданного источника S до конечной вершины KON за количество шаговое превышающее n-1. При этом разрешается лю­бое ребро проходить несколько раз.

[866] Найдите все возможные пути между двумя заданными вершинами графа и отметьте кратчайший путь между ними. Прохо­дить дважды через одну вершину нельзя.

[867] Найдите все возможные пути между тремя несмежными площадями и определите кратчайший путь между ними, если на­чальная и конечная точки движения совпадают.

[868] "Магазины в поселках". Построено k новых поселков, не­которые из которых соединены дорогами. Нужно построить мини­мальное количество магазинов в поселках так, чтобы из каждого поселка можно было добраться до магазина, проезжая не более од­ной дороги, и сумма длин дорог для всех поселков, необходимых для проезда в магазин, была минимальной.

[869] Найдите наименьший замкнутый путь в графе, проходя­щий через все вершины графа.

[870] Найдите наименьший замкнутый путь в графе, если при этом заходить в вершины A1, A2,...Ak запрещено, а в остальных нужно побывать только один раз.

[871] В трех вершинах графа нужно разместить три завода так, чтобы сумма минимальных расстояний до всех остальных вершин была минимальной.

[872]] Дан неориентированный граф. Определите вершины, из которых можно дойти до любой другой вершины графа, минуя не более двух ребер графа.

[873] Дан неориентированный граф. Определите вершины, из которых можно дойти до любой другой вершины графа, минуя не более трех ребер графа.

[874] Дан неориентированный граф. Определите те вершины графа, из которых можно достичь любой другой вершины графа, проходя не более, чем два ребра, если дополнительно добавить еще одно ребро. Укажите недостающее ребро для каждого такого слу­чая.

[875] В данном графе найдите тройку вершин А1, А2, A3 такую, чтобы все три вершины A1, A2, A3 были бы попарно связаны реб­рами графа, причем сумма длин ребер А1А2, А1А3, А2А3 была бы минимальной среди всех троек вершин данного графа, которые по­парно связаны между собой. Аналогично найдите тройку вершин В1, В2, ВЗ с максимальной суммой длин ребер. Из тройки A1, A2, A3 выбирается вершина NA, противолежащая большему ребру "треугольника" А1А2АЗ, а из тройки вершин В1, В2, В3 выделяется вершина KON, противолежащая меньшему ребру "треугольника" В1В2ВЗ. Найдите кратчайший путь между вершинами NA и KON и длину этого пути.

[876] (По условию задачи 25). В "минимальном треугольнике" найдите вершину, в которой сходятся два самых коротких ребра этого "треугольника".

[877] (По условию задачи 25). В "максимальном треугольнике'' найдите вершину, в которой сходятся два самых длинных ребра ^то­го "треугольника".

[878] (По условию задачи 25). Сосчитайте в графе количество "треугольников", то есть таких троек вершин А, В, С, для которых имеются ребра АВ, АС, ВС.

[879] Сосчитайте в графе количество "четырехугольников", то есть таких четверок вершин А, В, С, D, что существует четыре "последовательных" ребра, например, ребра АВ, ВС, CD, DA. Вы­пишите вершины всех "четырехугольников" и найдите "четырехугольник" с максимальным и минимальным периметром.

[880] Сосчитайте в графе количество "мнимых четырехугольни­ков", то есть таких четверок вершин А, В, С, D, для которых суще­ствуют соединяющие их ребра такие, чтобы две любые вершины этой четверки были связаны между собой без участия других вер­шин. Выпишите вершины всех "мнимых четырехугольников" и найдите среди них "четырехугольник" с минимальным "периметром".

[881] "Раскраска вершин графа". Задан неориентированный граф. Необходимо раскрасить вершины в минимальное число цветов так, чтобы любые две соседние связанные вершины были рас­крашены в разные цвета.

[882] "Время встречи роботов". Пункты с номерами 1, 2, ...n (n<=50) связаны сетью дорог, длины которых равны 1. Дороги про­ходят на разной высоте и пересекаются только в данных пунктах. В начальный момент времени 0 в некоторых пунктах находятся робо­ты, общее количество которых равно m (m=2 или m=3). Роботы на­чинают двигаться от пункта к пункту с постоянной скоростью неза­висимо друг от друга, меняя направление только в пунктах. Оста­новка роботов запрещена. Скорость i-ro робота равна 1 или 2. Робо­ты управляются таким образом, чтобы минимизировать время до встречи всех роботов в одном месте.

1) Требуется найти минимальное время t1, через которое может произойти встреча всех роботов в одном пункте, указать этот пункт или определить, что встреча всех m роботов в одном месте невоз­можна ни в какой момент времени (t>=0).

2) Если встреча возможна, то найдите время t2<=t1, через ко­торое встреча может произойти и вне пунктов.

3) Пусть роботам запрещена какая-либо остановка, а их ско­рость равна 1 или 2. При этих условиях найдите минимальное время 1, через которое произойдет встреча всех роботов в одном пункте, или сообщите, что встреча невозможна.

Вводится: n, m - связи между пунктами, скорости и пункты началь­ного расположения роботов.

Выводится: минимальное время и возможные пункты встречи, либо указание того, что встреча произойти не может.

[885] "Размещение заводов". Имеется k городов, связанных ме­жду собой сетью дорог. В них нужно разместить k заводов, выпус­кающих m1, m2, ... mk продукции. Продукция, производимая заво­дом в данном пункте, поровну распределяется между данным пунк­том и всеми пунктами, которые имеют прямую дорогу связи с дан­ным. Как расположить заводы, чтобы минимизировать транспорт­ные расходы.

И Г Р Ы.