2004-gre-cs-practice-book.pdf/Q41 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q41-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q41-4c9f66 == | == Вопрос: Q41-4c9f66 == | ||
| + | Для связного неориентированного графа ''G = (V, E)'', какое из следующих условий должно быть '''верно'''? | ||
| − | < | + | # <m>\sum_{v \in V} degree(v)</m> являются чётными |
| − | + | # <m>|E|\ge |V|-1</m> | |
| − | + | # ''G'' имеет по крайней мере одну вершину со степенью 1 | |
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | + | * Только 1 | |
| − | + | * Только 2 | |
| + | * Только 3 | ||
| + | * Правильный ответ: 1 и 2 | ||
| + | * 2 и 3 | ||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|30|41}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | * четность суммы степеней очевидна — каждое ребро в неориентированном добавляет двойку | |
| − | + | * связность дает второе | |
| − | + | * «треугольник» — опровергает третье | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 08:06, 15 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Алгоритмы на графах]] | |
Текущая версия на 08:06, 15 декабря 2024
Вопрос: Q41-4c9f66
Для связного неориентированного графа G = (V, E), какое из следующих условий должно быть верно?
- являются чётными
- G имеет по крайней мере одну вершину со степенью 1
Ответы
- Только 1
- Только 2
- Только 3
- Правильный ответ: 1 и 2
- 2 и 3
Объяснение
Исходники — вопрос 41 на 30 странице книги «2004-gre-cs-practice-book.pdf»
- четность суммы степеней очевидна — каждое ребро в неориентированном добавляет двойку
- связность дает второе
- «треугольник» — опровергает третье