29. Ориентированные графы. Полный ориентированный граф.

Δ| Если на каждом ребре задано направление, указное стрелкой, то граф называется ориентированным.

Матрица симметричности для ориентированных графов А=[a_ij].

a_ij=

	1	2	3	4	5	6	7
1	0	1	1	0	0	0	0
2	1	0	1	1	1	0	1
3	0	0	0	0	1	0	0
4	1	0	0	0	1	0	1
5	0	0	0	0	0	0	1
6	0	0	0	1	0	0	1
7	0	0	0	1	0	0	0

30. Графы с цветными ребрами. Свойства графов с цветными ребрами.

Рассмотрим графы соответствующие таким ситуациям, в которых одни пары элементов множества находятся между собой в одном отношении, другие пары этого множества в другом и т.д., но каждая пара в одном отношении (пр. среди участников шахматного турнира к какому-то моменту могут быть такие участники которые уже сыграли и такие которые не сыграли; среди множества стран есть страны, установившие между собой дипломатические отношения, а есть те страны, которые не установили).

На рисунках ребра соответствующие одному отношению закрашивают в один цвет, другому в другой и т.д. такие графы называют с цветными ребрами.

Красная – сплошная; синяя – штриховая.

Ex. 6 школьников учувствуют в шахматном турнире, который проводится в один круг. Докажите, что среди них всегда найдутся 3 участника турнира, которые провели все встречи между собой или не сыграли друг с другом ни одной партии.

► Любые 2 участника турнира непрерывно находятся между собой в одном из 2^х положений (либо сыграли, либо нет). Каждому участнику поставим в соответствие вершину графа. Пусть, красное ребро 2 уже сыгравших между собой участника, синее – не сыгравших.

Получили полный граф с 6^ю вершинами и ребрами 2^х цветов. Теперь для доказательства достаточно сказать, что в таком графе обязательно найдется треугольник с одноцветными сторонами.

Каждая вершина нашего графа принадлежит 5^и ребрам. Скольким ребрам одного цвета м/т принадлежать произвольная вершина 1^го графа?

5^ть принадлежащих одной вершине ребер могут быть окрашены без учета порядка следующим образом:

с с с с с

к с с с с

к к с с с

к к к с с

к к к к с

к к к к к

Т.е каждая вершина, принадлежит, по меньшей мере, ребрам оного цвета.

◄Свойства:

1^о. Любая вершина полного графа с 6^ю или более вершинами и ребрами двух цветов, принадлежит, по меньшей мере, 3^м ребрам одного цвета.

2^о. Среди любой вершины полного графа с 6^ю или более вершинами и ребрами двух цветов, найдется, по меньшей мере, один треугольник с одноцветными сторонами.

Задача.

На географической карте выбрано 5 городов. Известно, что среди них из любых 3^х найдутся 2 соединенные авиалиниями, и 2 не соединенных. Докажите что 1) каждый город соединен авиалиниями только с 2^я другими городми;2) Вылетев из любого города можно облететь остальные, побывав в каждом по одному разу и вернутся назад.

► Каждые 2 города находятся в одном из 2^х отношений, либо соединены, либо нет. Вершина – город, красное ребро – авиалиния, синее – нет.

По условию среди 3^х соединенных любых 3^х вершин одно – красное, второе – синее, это означает, что в графе нет ни одного треугольника с одноцветными сторонами, т.е. каждая вершина непременно принадлежит, либо 2^м красным, либо 2^м синим ребрам.

Поскольку в противном случае получается треугольник с одноцветными сторонами.

Остается показать, что в графе найдется 5^и угольник все ребра, которого красные. Выберем одну вершину А, тогда ребра АВ и АС будут красные, ребро ВС красным быть не может, следовательно красным может быть одно из ребер, либо СД, либо СЕ. Пусть красным будет ребро СД

3^о. Если в полном графе с 5^ю вершинами не найдется треугольник с одноцветными сторонами в виде 5 угольника с красными сторонами и синими диагоналями…

4^о. В любом полном графе с 6^ю или более вершинами и ребрами одного из 2^х цветов всегда найдется 2 различных треугольника с одноцветными сторонами. Эти 2 треугольника могут иметь общую вершину или ребро. Если 2 треугольника имеют общую вершину, то они называются сцепленными.

5^о. В полном графе с 17 вершинами и ребрами 3 цветов найдется …..

6^о. В полном графе с 8^ю, вершинами ребра которого окрашены в 2 цвета, найдутся 2 треугольника с одноцветными сторонами, которые не являются сцепленными.