Дискретная математика. Ерош И.Л - 102 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

102
Таблица 5.15
12345678
21876543
34128765
46513287
58761432
63287154
75432816
87654321
дем считать, что N – четное. Пе
ренумеруем игроков от 1 до N и
выпишем их номера так, как
указано в табл. 5.14. Затем за
черкнем номера на диагонали и
заменим их на 1. В таблице это
показано так: 2/1, 3/1, …, N/1.
Из построенной таблицы вид
но, что в первом туре играют 1й
и 2й игроки, 3й и Nй и т. д.
Число туров равно N–1 (мини
мально возможное), при этом в каждом туре заняты все участники.
Построим, например, турнирную таблицу для 7 игроков. Добавим
фиктивного игрока для того, чтобы число участников стало четным.
Таблица для 8 участников будет выглядеть так (табл. 5.15)
В первой строке построенной таблицы перечислены номера всех уча
стников. В первом туре играют пары из 1й и 2й строк. Во втором туре
играют пары из 1й и 3й строк и т. д. Один из игроков, например с
номером 8, является фиктивным.
5.13. Теорема Куратовского о плоских графах
Плоским графам посвящено очень большое число работ. Попытки
сформулировать необходимые и достаточные условия для того, чтобы
граф был плоским, неоднократно предпринимались. Наиболее сильным
результатом является теорема польского математика Куратовского.
Прежде чем сформулировать его теорему, сделаем несколько предвари
тельных замечаний.
1 23456....
N
21/2
NN1– N 2– N 3–
...43
341/32
NN1–
...65
4651/432
N
..87
. ..........
2/1 N 1+
NN1– N 2–
.....32
2/1 N 2+3 2
NN1–
. ..........
. ..........
. ..........
NN1– N 2–
......2
N 1/
Таблица 5.14

Страницы