Раскраска графов

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

Наименьшее возможное число цветов в раскраске называется хроматическим числом.

Множество вершин одного цвета называется одноцветным классом.

Граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы его ребра не пересекались.

Граф называется планарным, если его можно уложить на плоскости.

Эйлерова характеристика – это соотношения между числом вершин, ребер и граней.

Формула Эйлера: в связном планарном графе справедливо p-q+r=2, где

p - число вершин, q – число ребер, r – число граней плоского графа.

Следствие: если G – связный планарный граф (p>3), то q<=3p – 6.

Следствие: граф планарен тогда и только тогда, когда он не содержит в качестве подграфов ни G1, ни G2.

G1 G2

Следствие: в любом планарном графе существует вершина, степень которой не больше 5.

Теорема о пяти красках: всякий планарный граф можно раскрасить пятью красками.

Связный плоский мультиграф без мостов называется картой.

Мостом называется ребро, при удалении которого увеличивается число компонент графа.

Карта называется к-раскрашиваемой, если для неё существует к-раскраска.

Задания

1. Найдите хроматические числа графа:

2. Докажите, что для любого дерева хроматическое число не превосходит 2.

3. Пусть планарный граф с В вершинами и Р ребрами разбивает плоскость на Г частей (которые будем называть гранями). Доказать, что справедлива следующая формула Эйлера: В-Р+Г=2

4. Можно ли расположить на плоскости четыре точки и соединить их попарно шестью отрезками так, чтобы эти отрезки либо не пересекались, либо пересекались в данных точках?

5. Можно ли построить три дома, вырыть три колодца и соединить их тропинками так, чтобы тропинки не пересекались?

6. В стране Озерная 7 озер, соединенных между собой 10-ю каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?

7. Покажите, что добавление ребра к графу (при условии, что граф остаётся плоским) либо увеличивает число граней на 1, либо сокращает число связных компонент на 1.

8. Существует ли многогранник, у которого все грани семиугольные?

Релейно-контактные схемы.

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

Назовем контактом проводник, по которому проходит электрический ток.

Построим релейно-контактную схему для следующей функции:

xy

Если в схеме нет контакта проводников с обмотками реле, то такая схема называется контактной. (схема, изображенная выше, является контактной)

Если схема является контактной, то ее можно изобразить проще с помощью контактов, которые называются двухполюсниками.

Двухполюсники могут соединяться со своими полюсами, образуя контактную схему.

xy

Это есть ориентированный граф, у которого вершины – это полюса двухполюсников, а ребра – значения логических переменных.

На выходе получаем функцию проводимости этой контактной схемы f (x1, x2, …, xn).

Если направление тока изменить, то функция проводимости не изменится.

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

Любая простая цепь, которая соединяет начальную точку графа с конечной, называется значимой цепью.

Для того, чтобы на выходе был ток, необходимо, чтобы хотя бы 1 значимая цепь проводила ток.

Каждая значимая цепь реализует конъюнкцию, тогда функция проводимости реализует ДНФ.

Можно построить заданную схему с наперед заданными свойствами.

Например:

Для комитета из 3х человек для реализации тайного голосования из 3х голосов требуется составить эл. схему. Построить такую схему, чтобы в случае, если член комитета «за» - он нажимал кнопку, если «против» - то не нажимал. Когда большинство «за» - загоралась лампочка

А - 1ый «за»; В – 2ой «за»; С – 3ий «за»; D – результат.

A B C D

1 1 1 1

1 1 0 1

1 0 1 1

1 0 0 0

0 1 1 1

0 1 0 0

0 0 1 0

0 0 0 0

Схему, состоящую из 1 контакта, называют элементарной.

Способы соединения контактов:

• последовательный;

• параллельный.

Контактную схему назовем П-схемой, если она будет получена из элементарных за некоторое конечное число шагов при помощи последовательного и параллельного соединений.

Не любая схема может быть П-схемой.

Одну и ту же схему можно реализовать различным числом контактов. При реализации логической функции желательно строить схему, содержащую минимум контактов.

Схема называется минимальной, если она содержит наименьшее число контактов среди всех схем, имеющих 1 и ту же функцию.

В этой схеме все переменные являются существенными:

t = z = 0 y = 1 x!

t = z = 0 x = 1 y!

x = y = z = 0 t = 1 u!

x = y = z = 0 u = 1 t!

x = y = 1 u = 0 z!

Поскольку в этой схеме каждой переменной соответствует 1 контакт, то она является минимальной.

Если в семе все контакты относятся к разным переменным, причем все переменные входят в функцию существенно, то эта функция минимальна.

x1x2 … xn x1x2 … xn = (x1 x1)(x2 x2) … (xn xn)

Задачи

1. Реализуйте релейно-контактными схемами следующие функции:

а) xyz→t д) (x→y)(y→z)

б) xyz¬xy¬x¬y e) (x→y)(y→z)→(x→z)

в) (xy)¬z¬xzy ж) (x→y) →¬x(yz)

г) (xyz¬x)(y¬z) з) (x→(y→z)) →(y→¬x)

Какие из этих схем можно считать контактными? Нарисуйте соответствующие им контактные схемы.

2. Найдите функции проводимости для следующих контактных схем:

x

y

z

а

x

y

¬z

¬y

) б)

x

¬y

z

x

z

¬x

z

¬y

x

¬x

y

в

x

x

¬x

¬x

y

y

y

¬y

¬y

z

z

¬z

¬z

¬z

x

x

x

¬x

¬y

¬y

¬x

) г)

д

x

x

x

y

z

u

y

u

z

x

x

y

¬x

¬y

y

) е)

Если формулы допускают упрощения, то произведите упрощения и постройте соответствующие упрощенные схемы.

3. Укажите способ реализации функций контактными схемами при помощи КН-форм, аналогичный приведенному в п. 7 способу реализации при помощи ДН-форм.

4.

x	y	z	A
1	1	1	0
1	1	0	0
1	0	1	0
1	0	0	1
0	1	1	0
0	1	0	1
0	0	1	1
0	0	0	0

Постройте схему, соответствующую формуле А, заданной таблицей истинности.

5. Из контактов x, y, z составьте схему так, что бы она пропустила ток тогда, когда замкнуты какие-нибудь два из этих трех контактов.

6. Постройте контактную схему для игры: «По сигналу каждый игрок замыкает или размыкает переключатель, находящийся под его управлением. Если оба делают одно и то же, то выигрывает игрок А; если они делают противоположное, то выигрывает игрок В». Постройте такую схему, что бы в случае, когда выигрывает игрок А, зажигалась лампочка.

7. Придумайте такую контактную схему, что бы в большом зале можно было включать и выключить свет при помощи любого из четырех переключателей, расположенных на четырех стенах. (Это осуществимо, если свет включается, когда замкнуто честное число переключателей, и выключается, когда замкнуто нечетное число переключателей. Почему это решает задачу?)

8. Комитет состоит из пяти членов. Решения принимаются большинством голосов, однако, если председатель голосует «против», решение не может быть принято. Постройте такую схему, чтобы голосование каждого члена комитета за принятие решения производилось путем нажатия кнопки, а лампочка загоралась в том и только том случае, если решение принято.

9. Постройте такую схему, чтобы экзаменующийся мог отвечать, нажимая кнопки, соответствующие тем вопросам, на которые он хочет дать ответ «да», и чтобы эта схема показывала число правильных ответов с помощью горящей лампочки, соответствующей числам 0. 1. 2. 3. 4. 5 правильных ответов.

10. Докажите, что «мостик» не является П схемой.

11. Постройте заданные схемы:

A	X	Y	U	A
0	1	0	0	1
1	0	1	0	0
0	0	0	0	0
1	0	1	0	0
1	1	1	1	0
0	1	1	1	0
0	0	1	1	1
1	0	0	1	1
0	1	1	0	0

X	Y	Z	A
0	0	0	1
0	1	1	0
0	0	1	0
1	1	1	0
1	1	1	1
0	1	0	0
1	0	1	0
1	1	1	1

X	Y	Z	A
0	1	1	0
1	1	1	0
1	0	0	1

X	Y	Z	U	A
1	0	1	0	0
0	1	0	0	0
0	1	1	0	1
1	0	1	1	1
1	0	1	1	1
0	0	0	1	0

49