Докажите дерево двудольный граф

Содержание

Двудольные графы
Ориентированные графы и мультиграфы
Важнейшие классы графов

Двудольные графы

Является ли двудольным графом

 простая цепь?  дерево?  полный граф?

Докажите, что дерево является двудольным графом. Какие деревья являются полными двудольными графами?
В теннисном турнире каждый игрок команды «синих» встречается с каждым игроком команды «красных». Число игроков в командах одинаково и не более восьми. «Синие» выиграли в четыре раза больше встреч, чем «красные». Сколько человек в каждой из команд?
Школьники решали 16 задач. Каждый из 16 школьников решил по четыре задачи, и каждая задача была решена четырьмя школьниками. Доказать, что можно организовать разбор задач так, чтобы каждый рассказал одну решенную им задачу и чтобы все задачи были разобраны.
Каждый из учеников 9 «А» класса дружит с тремя учениками 9 «Б» класса, а каждый из учеников 9 «Б» класса дружит с тремя учениками 9 «А» класса. Докажите, что число учеников в обоих классах одинаково.
Строительному управлению для выполнения работы требуются каменщик, плотник, водопроводчик и слесарь. На эти должности имеются пять претендентов: один может работать каменщиком, другой – плотником, третий – каменщиком и водопроводчиком и еще двое имеют по две специальности – водопроводчика и слесаря. Можно ли охватить весь фронт работ (используя четверых рабочих)? Если да, то подробно проверьте выполнение условия теоремы Холла.
Десять кандидатов готовятся к двум космическим экспедициям на Марс. Поскольку экспедиции будут продолжаться несколько лет, а их участники окажутся в замкнутом пространстве небольшого объема, то большое значение приобретает психологическая совместимость членов экипажа. Путем тестирования установлены пары кандидатов, присутствие которых в одной и той же экспедиции было бы нежелательным. Результаты тестирования отражены в таблице. (Если на пересечении I строки j столбца находится знак «+», то участие I и j кандидатов в одной экспедиции нежелательно.) Разделите кандидатов на две группы для участия в экспедициях.

В школе 4 кружка: домоводство, математический кружок, компьютерный клуб и кружок английского языка. Пять человек из класса посещают эти кружки, причем один и тот же ученик может являться членом нескольких кружков. Можно ли выбрать старосту в каждом кружке так, чтобы ни один человек не был старостой сразу в двух кружках в следующих случаях:

Кружок домоводства посещают 1, 3 и 4 ученики, математический кружок – 1, 4 и 5, компьютерный клуб – 2, 3 и 5, кружок английского языка – 2, 4 и 5.
Кружок домоводства посещают 1 и 3 ученики, математический кружок – 2 и 3, компьютерный клуб – 2 и 1, кружок английского языка – 3.
Кружок домоводства посещают 1, 3 и 4 ученики, математический кружок – 2 и 5, компьютерный клуб – 2 и 5, кружок английского языка – 2.

Ориентированные графы и мультиграфы

Решите задачу 35. Граф может быть орграфом или мультиграфом.
В некотором государстве каждый город соединен с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы, выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?
Докажите, что на ребрах связного графа можно так расставить стрелки, чтобы из некоторой вершины можно было добраться по стрелкам до любой другой.
Доказать, что связный граф можно обойти, проходя по каждому ребру дважды.
Изобразите матрицы смежности и инциденций ориентированного графа:

Дана матрица смежности. Изобразить граф, ей соответствующий.

а) б)

Из города А в город В ведут несколько дорог (карта дорог на рисунке). Найдите число маршрутов из А в В, учитывая, что при движении необходимо всегда приближаться к В.

Может ли в ориентированном графе полустепень захода каждой вершины быть равна 3, а полустепень исхода – 4?
В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.
В некотором государстве 101 город. а) Каждый город соединен с каждым дорогой с односторонним движением, причем в каждый город входит 50 дорог, и из каждого города выходит 50 дорог. Докажите, что из любого города можно доехать в любой другой, проехав не более чем по двум дорогам; б) Некоторые города соединены дорогами с односторонним движением, причем в каждый город входит 40 дорог, и из каждого города выходит 40 дорог. Докажите, что из любого города можно добраться до любого другого, проехав не более чем по трем дорогам.
В стране Ориентация на всех дорогах введено одностороннее движение, причем из любого города в любой другой можно добраться, проехав не более чем по двум дорогам. Одну дорогу закрыли на ремонт так, что из каждого города по-прежнему можно добраться до каждого. Докажите, что для любых двух городов это можно сделать, проехав не более, чем по трем дорогам.
Найдите компоненты сильной связности графа, заданного матрицей смежности:

Найдите компоненты сильной связности графа:

Решите задачу 62, считая, что заданы матрицы смежности ориентированного графа.
Дана матрица смежности графа. Определить, является ли он эйлеровым. Ответ обоснуйте.

На ребрах связного графа расставлены стрелки так, что для каждой вершины числа входящих и выходящих ребер равны. Докажите, что, двигаясь по стрелкам, можно добраться от любой вершины до любой другой.
По заданной матрице весов графа G найти величину минимального пути и сам путь от вершины 1 до вершины 6 по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами:

В связном неориентированном графе степени всех вершин четны. Докажите, что на ребрах этого графа можно расставить стрелки так, чтобы выполнялись следующие условия: а) двигаясь по стрелкам, можно добраться от любой вершины до любой другой; б) для каждой вершины числа входящих и выходящих ребер равны.
На плоскости отмечено некоторое конечное число точек. Некоторые пары точек являются началами и концами векторов, причем число векторов, выходящих из любой точки, равно числу входящих в неё. Найдите сумму векторов.
В некоторой стране каждый город соединен с каждым дорогой с односторонним движением. Докажите, что найдется город, из которого можно добраться в любой другой.
Несколько команд сыграли между собой круговой турнир по волейболу. Будем говорить, что команда А сильнее команды В, если либо А выиграла у В, либо существует команда С такая, что А выиграла у С, а С – у В. а) Докажите, что есть команда, которая сильнее всех. б) Докажите, что команда, выигравшая турнир, сильнее всех.
В одном государстве 100 городов, и каждый соединен с каждым дорогой с односторонним движением. Докажите, что можно поменять направление движения на одной дороге так, чтобы от любого города можно было доехать до любого другого.
20 команд сыграли круговой турнир по волейболу. Докажите, что команды можно занумеровать числами от 1 до 20 так, что 1-я команда выиграла у 2-й, 2-я — у 3-й, . 19-я у 20-й.
Докажите, что если победитель турнира по волейболу, проведенного по круговой системе, проиграл команде В, то существует команда С, выигравшая у В, у которой выиграл победитель.
Какие-то две команды набрали в круговом волейбольном турнире одинаковое число очков. Докажите, что найдутся команды А, В и С такие, что А выиграла у В, В выиграла у С, а С выиграла у А.

Источник

Важнейшие классы графов

Деревом называется связный граф , не имеющий циклов. В графе без циклов, таким образом, каждая компонента связности является деревом. Такой граф называют лесом .

P_<n data-lazy-src=

Из теоремы 2 «Маршруты, связность, расстояния» следует, что во всяком дереве, в котором не меньше двух вершин, имеется вершина степени 1. Такие вершины называют висячими вершинами , или листьями . В действительности легко доказать, что в каждом дереве не меньше двух листьев, а цепь »/> — пример дерева, в котором точно два листа.

В следующих двух теоремах устанавливаются некоторые свойства деревьев.

Теорема 1. Граф с ребрами является деревом тогда и только тогда, когда он удовлетворяет любым двум из следующих трех условий:

m=n-1

(1) связен;
(2) не имеет циклов;
(3) .

Первые два условия вместе составляют определение дерева. Покажем, что выполнение любых двух из условий (1)-(3) влечет за собой выполнение третьего.

(1) и (2) $\Rightarrow$ (3). Индукция по числу вершин. При n=1 утверждение очевидно. При $n\ge 2$ в дереве имеется хотя бы один лист. Если из дерева удалить лист, то снова получится дерево, так как циклов не появится, а связность, очевидно, сохранится. В этом новом дереве n-1 вершин и, по предположению индукции, n-2 ребра. Следовательно, в исходном дереве было n-1 ребро.

(2) и (3) $\Rightarrow$ (1). Пусть в графе, не имеющем циклов, n-1 ребро, а его компонентами связности являются G_<1 data-lazy-src= ,G_\ldots G_»/>, причем вершин, $i=1\ldots k$ . Каждая компонента является деревом, поэтому, как доказано выше, число ребер в равно n_-1 , а всего ребер в графе $\suml_<i=1 data-lazy-src=$ ^\left(n_ -1\right) =n-k=n-1″/>. Значит, $\Rightarrow$ (2). Рассмотрим связный граф с n-1 ребром. Если бы в нем был цикл, то, удалив любое цикловое ребро, мы получили бы связный граф с меньшим числом ребер. Можно продолжать такое удаление ребер до тех пор, пока не останется связный граф без циклов, то есть дерево. Но ребер в этом дереве было бы меньше, чем n-1 , а это противоречит доказанному выше.

Теорема 2. Если — дерево, то

в любая пара вершин соединена единственным путем;
при добавлении к любого нового ребра образуется цикл;
при удалении из любого ребра он превращается в несвязный граф .

Существование пути между любыми двумя вершинами следует из связности дерева. Допустим, что в некотором дереве существуют два различных пути, соединяющих вершины и . Начальные отрезки этих путей совпадают (оба пути начинаются в одной и той же вершине ). Пусть — последняя вершина этого совпадающего начала, а после в одном пути следует вершина y_<1 data-lazy-src= »/>, а в другом — вершина $\left(x,y_<1 data-lazy-src=$ \right)»/>. Если его удалить из графа, то в оставшемся подграфе вершины будут соединимыми — соединяющий их маршрут можно построить так: взять отрезок первого пути от y_<1 data-lazy-src= »/> до до , взятый в обратном порядке. Но это означает, что ребро $\left(x,y_<1 data-lazy-src=$ \right)»/> не является перешейком. Однако из теоремы 4 «Маршруты, связность, расстояния» следует, что в дереве каждое ребро является перешейком. Этим доказано утверждение 1). Утверждения 2) и 3) следуют из 1).

Отметим, что единственный путь , соединяющий две вершины дерева, всегда простой (если путь не является простым, в нем обязательно содержится цикл).

Источник