Решение задач «Теория графов (планарные графы, унициклические графы)»,
Дискретная математика в Новосибирске

Планарные графы. Формула Эйлера 1. Какое минимальное число пересечений ребер может получиться, если нарисовать на плоскости K3,3? 2. Пусть G - связный граф с 7 вершинами, 16 ребрами, степень каждой вершины которого не менее 4. Какие из следующих утверждений являются верными? а) Граф G планарен. б) Граф G не является планарным. в) Граф G может быть как планарным, так и не планарным. г) В графе G существует подграф, гомеоморфный K3,3. д) В графе G существует подграф, гомеоморфный K5. 3. При доказательстве оценки хроматического числа связного планарного устанавливается, что в планарном графе есть вершина степени, не превосходящей 5. Какое наибольшее число вершин степени, не превосходящей 5, гарантируют неравенства v≥3, e≤3v−6 в связном (необязательно планарном) графе? а) 1 б) 2 в) 3 г) 4 д) 5 Тест. Унициклические графы. Эйлеровы циклы. 1. Отметьте верные утверждения(множественный выбор): а) В любом графе есть не более одного эйлерова цикла. б) Любой граф, множество ребер которого представляется в виде дизъюнктного объединения простых циклов, является эйлеровским. в) В связном графе эйлеров цикл проходит через все вершины. 2. При каких условиях в графе Kn есть эйлеров цикл (один вариант)? а) При n≥3 нечетном. б) При n≥3. в) При n≥3 четном. г) При n≥12 делящемся на 6. 3. При каких условиях в графе Km,n есть эйлеров цикл (один вариант)? а) При m≥2, n≥2 четных. б) При m=n≥2. в) При m=n≥3. г) При m≥2, n≥2 нечетных. 4. Пусть G - это связный граф с n вершинами и n+1 ребрами. Сколько различных простых циклов может быть в графе G (один вариант)? а) 2,3 б) 2,4 в) 1,2,3 г) 2,3,4 5. Сколько различных простых циклов содержится в Kn (один вариант)? а) ∑k=1nCnkk! б) ∑k=3nCnk(k−1)!/2 в) ∑k=3nk! г) n!