Страница 70 номер 120, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
В любом ли графе можно ориентировать все рёбра так, чтобы не получилось ни одного ориентированного цикла (чтобы ни из какой вершины нельзя было вернуться в неё, следуя вдоль рёбер)?
Петля — это цикл длины 1: как её ни ориентируй, из её вершины по этому ребру можно вернуться в ту же вершину. Значит, в графе с петлёй нужным образом ориентировать рёбра невозможно.
Пусть теперь в графе петель нет и вершин в нём \(n\). Пронумеруем вершины числами 1, 2, …, \(n\) в любом порядке и каждое ребро направим от вершины с меньшим номером к вершине с бо́льшим: так можно поступить с каждым ребром, потому что концы ребра — различные вершины и номера у них разные.
Возьмём любой путь, идущий по стрелкам. При каждом переходе мы попадаем в вершину с бо́льшим номером, поэтому номер вершины по ходу пути всё время растёт, и вернуться в вершину, из которой мы вышли, невозможно: её номер меньше номера любой следующей вершины пути. Ориентированных циклов в таком графе нет.
Кратные рёбра этому не мешают: два ребра, соединяющие одни и те же вершины, получат одно и то же направление, и вернуться назад по второму ребру нельзя.
Ответ: в любом графе без петель — да: достаточно пронумеровать вершины и направить каждое ребро от меньшего номера к большему; если же в графе есть петля, то нет, потому что петля сама является ориентированным циклом.
В любом ли графе можно ориентировать все рёбра так, чтобы не получилось ни одного ориентированного цикла (чтобы ни из какой вершины нельзя было вернуться в неё, следуя вдоль рёбер)?
Разберём отдельно графы с петлями и графы без петель.
Петля — это цикл длины 1. Как её ни ориентируй, из её вершины по этому ребру можно вернуться в ту же вершину, то есть ориентированный цикл получается сразу. Значит, в графе с петлёй нужным образом ориентировать рёбра невозможно.
Пусть теперь в графе петель нет и вершин в нём \(n\). Пронумеруем вершины числами 1, 2, …, \(n\) в любом порядке и каждое ребро направим от вершины с меньшим номером к вершине с бо́льшим номером. Так можно поступить с каждым ребром: концы ребра — различные вершины, и номера у них разные.
Возьмём любой путь, идущий по стрелкам. При каждом переходе по ребру мы попадаем в вершину с бо́льшим номером, поэтому номер вершины по ходу движения всё время растёт. Значит, вернуться в вершину, из которой мы вышли, невозможно: её номер меньше номера любой следующей вершины пути. Следовательно, ориентированных циклов в таком графе нет.
Кратные рёбра этому не мешают: два ребра, соединяющие одни и те же вершины, получат одно и то же направление, и вернуться назад по второму ребру нельзя.
Ответ: в любом графе без петель — да: достаточно пронумеровать вершины и направить каждое ребро от меньшего номера к большему; если же в графе есть петля, то нет, потому что петля сама является ориентированным циклом.
