II. Задачи для усвоения материала. I. Необходимые определения и формулировки теорем

I. Необходимые определения и формулировки теорем.

1. Что такое «орграф»?

2. Что такое «граф»?

3. Для каких объектов применимы термины: «вершина», «дуга», «ребро» «путь», «цепь», «контур», «цикл»?

4. Что такое «вершина», «дуга», «ребро»?

5. Что такое «путь», «цепь»?

6. Что такое «контур», «цикл»?

1. Представить карту бывшего СССР в виде плоского графа (вершины – республики, ребра - границы).

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

3. Двое играют в игру "ним": Имеется две кучки по 2 спички в каждой. Игрок может взять любое (ненулевое) число спичек, но только из одной (по его выбору) кучки. Игрок, забравший последнюю спичку, проигрывает. Требуется:

а) изобразить игру в виде орграфа (вершины – позиции, дуги – все ходы);

б) разработать оптимальную стратегию игры, анализируя пути из исходной позиции выигрышной. Кто выигрывает при правильной игре обоих?

4. То же, если в одной кучке 2 спички, а в другой 3 спички.

5. То же, если в обеих кучках по 3 спички.

6. То же, если всего три кучки: в первой 1 спичка, во второй – 2 спички, а в третьей 3 спички.

7. Двое играют в следующую игру: Первый пишет любую из цифр 1,2 или 3, второй приписывает справа любую из этих же цифр, первый приписывает справа любую из этих же цифр. Если полученное трёхзначное число – простое, то выигрывает первый игрок, если составное – то второй игрок.

а) изобразить игру в виде орграфа (вершины – позиции, дуги – все ходы);

б) разработать оптимальную стратегию игры, анализируя пути из исходной позиции выигрышной. Кто выигрывает при правильной игре обоих?

8. В группе по изучению иностранных языков Александр знает телефоны Татьяны, Ирины, Максима и Олега. Андрею известны номера Ольги, Олега, Татьяны. Ирина имеет телефон Александра, Татьяны, Ольги. Максим знает только телефон Олега. Постройте граф связей данной группы, если все имена участников различны.

9. Постройте граф для решения следующей задачи:

Жили четыре друга. Звали их Альберт, Карл, Дитрих и Фридрих. Фамилии друзей те же, что и имена, только так, что ни у кого из них имя и фамилия не были одинаковыми, кроме того, фамилия Дитриха не Альберт. Известно, что имя мальчика, у которого фамилия Фридрих, есть фамилия того мальчика, имя которого - фамилия Карла.

(В качестве вершин используйте имена и фамилии, в качестве рёбер соотношение «не совпадает»).

Определите фамилию и имя каждого мальчика.

Дата добавления: 2014-11-25