ВУЗ:
Составители:
Рубрика:
31
вовать маршруту патрулирования. 12. Рассмотрим орграф
G
,
задающий движение в городе. Из условия задачи следует, что
для вершин графа
G
выполняется равенство
vdvd
.
Следовательно, граф
G
эйлеров, и эйлеров цикл определит
нужный маршрут патрулирования. 13. Точки плоскости вместе с
векторами образуют орграф
G
. Возможно, орграф
G
, задаю-
щий векторы в задаче, не является связным. Применим теоре-
му 5.4 к каждой связной части орграфа, получим разбиение век-
торов на контуры. Сумма векторов, принадлежащих одному
контуру, равна нулю. Следовательно, сумма всех векторов равна
нулевому вектору.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Березина Л. Ю. Графы и их применение. М.: Книжный
дом «Либроком», 2009.
2. Мельников О. И. Теория графов в занимательных задачах.
М.: Книжный дом «Либроком», 2008.
3. Оре О. Теория графов. М.: Наука, 1980.
4. Поздняков С.Н., Рыбин С. В. Дискретная математика. М.:
Издательский центр «Академия», 2008.
5. Алексеев В. Б., Поспелов А. Д. Дискретная математика.
М.: МГУ им. М. В. Ломоносова, 2002.
6. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука,
1974.
7. Краснов М. Л., Киселев А. И., Макаренко Г. И. Вся выс-
шая математика. Т. 7. М.: КомКнига, 2006.
