Е. К. Годунова Введение в теорию графов Индивидуальные задания Москва 2012 Московский педагогический государственный университет Министерство образования и науки Российской Федерации федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский педагогический государственный университет» Е. К. Годунова Введение в теорию графов Индивидуальные задания МПГУ Москва-2012 УДК 519.17(075.8) ББК 22.174.2 Г593 Г593 Годунова Е. К. <...> В пособии приведены индивидуальные задания по основным разделам и ее приложений: изоморфия, метрика, эйлеровы и гамильтоновы графы, паросочетания в двудольном графе, система фундаментальных циклов по Кирхгофу, планарность, раскраска карт и вершин графов и др. <...> Одно из заданий посвящено организации повторения теорем теории графов. <...> Поиск в графах эйлеровых циклов и эйлеровых цепей……… 18 Задание 11. <...> Построение символа (T) дерева T , покрывающего данныйграф, и решение обратной задачи (алгоритм Пруфера)…………… 29 Задание 17. <...> Задайте граф 1G вашего варианта тремя способами: а. б. в. <...> Сформулируйте ответ на вопрос: «Как способы задания графа (а), (б), (в) из пункта 1 дают возможность определить смежность вершин, смежность ребер, инцидентность вершин и ребер? <...> Р и в простом цикле n перечислением вершин а. б. в. г. C ? <...> Выделите на диаграмме графа 2G , пометив его вершины, и задайте маршрут, не являющийся цепью, цепь, не являющуюся простой, простую цепь 6Р , цикл, не являющийся простым, 4 , с 4 ; б) ребра, д. <...> Приведите примеры диаграмм связного графа и графа с тремя компонентами связностей. <...> (Для проверки используйте утверждение: суммарное число ребер в графах G и G равно числу ребер полного графа с таким же числом вершин. <...> Во втором случае тоже рассмотрите две возможности: произвольно выбранные вершины u и принадлежат разным компонентам связности графа G или одной. <...> В последнем случае следует выбрать вспомогательную вершину W на другой компоненте связности <...>
Введение_в_теорию_графов._Индивидуальные_задания_(1).pdf
УДК 519.17(075.8)
ББК 22.174.2
Г593
Г593 Годунова Е. К. Введение в теорию графов. Индивидуальные задания.
– М.: МПГУ, 2012. – 44 с.
В пособии приведены индивидуальные задания по основным
разделам и ее приложений: изоморфия, метрика, эйлеровы и гамильтоновы
графы, паросочетания в двудольном графе, система
фундаментальных циклов по Кирхгофу, планарность, раскраска
карт и вершин графов и др. Задания предназначены для организации
самостоятельной работы студентов по курсу. Одно из заданий
посвящено организации повторения теорем теории графов. Пособие
дополнено приложением, содержащим советы и вопросы общего характера,
помогающие усвоить основные факты теории.
ISBN 978-5-4263-0104-7
© МПГУ, 2012
© Издательство «Прометей», 2012
2
Стр.2
Содержание
Задание 1. Определение графа. Первоначальные понятия………………... 4
Задание 2. Подграфы, простейшие виды графов…………………………... 7
Задание 3. Изоморфизм графов……………………………………………... 8
Задание 4. Перечисление графов……………………………………………. 10
Задание 5. Метрика в графе…………………………………………………. 10
Задание 6. Степени вершин графа…………………………………………... 12
Задание 7. Граф Московского метрополитена……………………………... 13
Задание 8. Двухцветная раскраска ребер графа……………………………. 14
Задание 9. Головоломка с кубиками………………………………………... 16
Задание 10. Поиск в графах эйлеровых циклов и эйлеровых цепей……… 18
Задание 11. Обход лабиринта……………………………………………….. 19
Задание 12. Гамильтоновы циклы…………………………………………... 21
Задание 13. Поиск наибольших паросочетаний в двудольном графе…….. 24
Задание 14. Системы фундаментальных циклов по Кирхгофу…………… 27
Задание 15. Экстремальное дерево………………………………………….. 28
Задание 16. Построение символа (T) дерева T , покрывающего
данныйграф, и решение обратной задачи (алгоритм Пруфера)…………… 29
Задание 17. Планарные графы и их плоские укладки……………………... 30
Задание 18. Раскраска карт и вершин графов………………………………. 33
Задание 19. Матрицы смежностей и инциденций…………………………. 35
Задание 20. Социометрические матрицы, турниры,
ранги индивидуумов………………………………………………………….. 37
Задание 21. Определение порядка следования элементов
по заданному списку предпочтений…………………………………………. 37
Задание 22. Повторение теорем теории графов……………………………. 40
Приложение. Советы и вопросы,
помогающие усвоить доказательства теорем……………………………….. 42
3
Стр.3