На рисунке показана административных округов Москвы. карта Администативные округа Москвы: 1. Центальный (ЦАО) 2. Северо-Западный (СЗАО) 3. Северный (САО) 4. Северо-Восточный (СВАО) 5. Восточный (ВАО) 6. Юго-Восточный (ЮВАО) 7. Южный (ЮАО) 8. Юго-Западный (ЮЗАО) 9. Западный (ЗАО) 10. Новомосковский (НАО) 11.Троицкий (ТАО) 12.Зеленоградский (ЗелАО) Постройте граф, вершины которого соответствуют административным огругам. Ребро, соединяющее две вершины, означает, что два округа граничат друг с другом. Есть ли в построенном графе изолированные вершины? (Изолированная вершина - вершина, которая не связана рёбрами ни с какой другой вершиной, т.е. ее степень равна 0).

Давайте разберемся с задачей пошагово. **Задача:** Построить граф, вершинами которого являются административные округа Москвы. Ребра отражают границы между соседствующими округами. Затем определить, есть ли в этом графе изолированные вершины (то есть такие округа, у которых нет соседей). --- ### Шаг 1. Определение вершин графа Вершинами графа будут все указанные округа: 1. Центральный (ЦАО) 2. Северо-Западный (СЗАО) 3. Северный (САО) 4. Северо-Восточный (СВАО) 5. Восточный (ВАО) 6. Юго-Восточный (ЮВАО) 7. Южный (ЮАО) 8. Юго-Западный (ЮЗАО) 9. Западный (ЗАО) 10. Новомосковский (НАО) 11. Троицкий (ТАО) 12. Зеленоградский (ЗелАО) --- ### Шаг 2. Определение границ между округами Нам нужно понять, какие округа граничат друг с другом. Обычно округа, расположенные по соседству, имеют общие границы. Введите их предполагаемые соседства: - **ЦАО** граничит с: - ЗАО - ЮАО - ВАО - СЗАО - САО - **СЗАО** граничит с: - ЦАО - ЗАО - ЮЗАО - ЗелАО (Зеленоградский адміністративный округ) - **САО** граничит с: - ЦАО - СЗАО - ВАО - ЮАО - **СВАО** граничит с: - ВАО - ЮВАО - ЗелАО - **ВАО** граничит с: - ЦАО - САО - СВАО - ЮВАО - **ЮВАО** граничит с: - ВАО - ЮЗАО - ЮАО - ЗелАО - **ЮЗАО** граничит с: - ЮВАО - ЮАО - ЗАО - СЗАО - **ЗАО** граничит с: - ЦАО - ЮЗАО - ЮАО - СЗАО - ЗелАО - **НАО**: находится на юге, граничит с: - ЮЗАО - Троицким (ТАО) - **ТАО** (Троицкий): граничит с: - НАО - **ЗелАО** (Зеленоградский): граничит с: - СЗАО - СВАО - ЮВАО - ЮЗАО --- ### Шаг 3. Построение графа Теперь, исходя из описанных границ, составим список ребер (без повторений): - (ЦАО, ЗАО) - (ЦАО, ЮАО) - (ЦАО, ВАО) - (ЦАО, СЗАО) - (ЦАО, САО) - (СЗАО, ЗАО) - (СЗАО, ЮЗАО) - (СЗАО, ЗелАО) - (САО, ВАО) - (САО, ЮАО) - (ВАО, ЮВАО) - (ВАО, ЗелАО) - (ЮВАО, ЮЗАО) - (ЮВАО, ЮАО) - (ЮВАО, ЗелАО) - (ЮЗАО, ЮАО) - (ЮЗАО, ЗЕЛАО) - (ЮЗАО, ЗАО) - (ЮЗАО, СЗАО) - (ЗАО, ЮАО) - (ЗАО, ЮЗАО) - (ЗАО, СЗАО) - (ЗАО, ЗелАО) - (НАО, ТАО) - (НАО, ЮЗАО) - (ТАО, НАО) - (ЗелАО, СЗАО) - (ЗелАО, СВАО) - (ЗелАО, ЮВАО) - (ЗелАО, ЮЗАО) --- ### Шаг 4. Проверка наличия изолированных вершин Из полученного списка видно, что: - Все округа имеют хотя бы одно ребро (границу с другим округом). Исключим вариант, что есть изолированные вершины. Например, если какой-то округ не граничит со никем, то его степень равна 0. В нашем случае каждая вершина связана хотя бы с одним округом. --- ### **Ответ:** **В построенном графе нет изолированных вершин**, поскольку все округа имеют хотя бы одного соседа. --- Если потребуется граф в виде схемы или более подробное описание, скажите!