1. Побудуйте граф на множині бінарного відношення числа х та у не взаємно прості. Побудуйте матрицю суміжностей та матрицю інциденцій цього графа.
2. Чи можна вершини куба занумерувати різними тризначними числами, складеними із цифр 1 і 2 так, щоб номери двох сусідніх вершин відрізнялись не менше ніж у двох розрядах.
3. У деякому товаристві кожні двоє знайомих не мають спільних знайомих, а кожні двоє незнайомих мають також двоє спільних знайомих. Довести, що в цьому товаристві всі мають однакове число знайомих.
4. У кімнаті знаходиться 10 осіб, причому серед кожних трьох із них є двоє знайомих між собою. Довести, що знайдуться чотири особи, кожна пара з яких знайомі між собою.
Варіант№20
1.
Побудуйте граф на множині
бінарного
відношення
числа
–
непарне число. Побудуйте матрицю
суміжностей та матрицю інциденцій цього
графа.
2. На кубі відмічено вершини та центри граней і проведено діагоналі всіх граней. Чи можна по відрізкам цих діагоналей обійти всі відмічені точки, побувавши в кожній із них рівно по одному разу?
3. Дано замкнену ламану, яка сама себе перетинає, причому кожну ланку вона перетинає точно один раз. Довести, що число ланок парне.
4. Як з'єднати 50 міст найменшим числом авіаліній так, щоб з довільного міста можна було потрапити в довільне, зробивши не більше двох пересадок?