Question

10 міст з'єднані авіалінія. Довести що хоча б два міста мають однакову кількість авіаліній​

Answer 1

Ответ:

Оскільки вам потрібно довести, що хоча б два міста мають однакову кількість авіаліній, спробуйте використати теорему про кількість зв'язків у графі.

Якщо в уявленні кожен місто представлено вузлом, а авіалінії - це зв'язки між містами (граф без орієнтації), то скористайтеся теоремою про розділення графа на частини.

Теорема говорить, що якщо у графі є 10 вузлів і кожен вузол має ступінь (кількість зв'язків) щонайменше 9, то є два вузли з однаковою ступенем (кількістю зв'язків).

Отже, в умові, якщо у 10 міст є з'єднання через авіалінії, за цією теоремою, хоча б два міста повинні мати однакову кількість авіаліній.

Объяснение: