В пособии приведены индивидуальные задания по основным разделам и ее приложений: изоморфия, метрика, эйлеровы и гамильтоновы графы, паросочетания в двудольном графе, система фундаментальных циклов по Кирхгофу, планарность, раскраска карт и вершин графов и др. <...> Одно из заданий посвящено организации повторения теорем теории графов. <...> Поиск в графах эйлеровых циклов и эйлеровых цепей……… 18 Задание 11. <...> Построение символа (T) дерева T , покрывающего данныйграф, и решение обратной задачи (алгоритм Пруфера)…………… 29 Задание 17. <...> Задайте граф 1G вашего варианта тремя способами: а. б. в. <...> Сформулируйте ответ на вопрос: «Как способы задания графа (а), (б), (в) из пункта 1 дают возможность определить смежность вершин, смежность ребер, инцидентность вершин и ребер? <...> Р и в простом цикле n перечислением вершин а. б. в. г. C ? <...> Выделите на диаграмме графа 2G , пометив его вершины, и задайте маршрут, не являющийся цепью, цепь, не являющуюся простой, простую цепь 6Р , цикл, не являющийся простым, 4 , с 4 ; б) ребра, д. <...> Приведите примеры Какой граф называется дополнением графа G? <...> Есть ли среди этих дополнений несвяздиаграмм связного графа и графа с тремя компонентами связностей. <...> (Для проверки используйте утверждение: суммарное число ребер в графах G и G равно числу ребер полного графа с таким же числом вершин. <...> Во втором случае тоже рассмотрите две возможности: произвольно выбранные вершины u и принадлежат разным компонентам связности графа G или одной. <...> В последнем случае следует выбрать вспомогательную вершину W на другой компоненте связности. <...> 7 , 8 Докажите теорему: «Либо граф G, либо его дополнение G является 5 6 Задание 2 Подграфы. <...> 5 , 5 , Выделите минимальный связный остовный подграф в каждом из графов K W K3,3 ,C 7 . <...> Любое ли число ребер может входить в полный граф, в полный двудольный граф? <...> Сформулируйте и докажите отвечающие на поставленный вопрос теоремы. <...> Сформулируйте определения понятий «остовный подграф», «полный двудольный граф <...>
Введение_в_теорию_графов._Индивидуальные_задания.pdf
УДК 519.17(075.8)
ББК 22.174.2
Г593
Г593 Годунова Е. К. Введение в теорию графов. Индивидуальные задания.
–М.: МПГУ, 2012. – 44 с.
В пособии приведены индивидуальные задания по основным
разделам и ее приложений: изоморфия, метрика, эйлеровы и гамильтоновы
графы, паросочетания в двудольном графе, система
фундаментальных циклов по Кирхгофу, планарность, раскраска
карт и вершин графов и др. Задания предназначены для организации
самостоятельной работы студентов по курсу. Одно из заданий
посвящено организации повторения теорем теории графов. Пособие
дополнено приложением, содержащим советы и вопросы общего характера,
помогающие усвоить основные факты теории.
ISBN 978-5-4263-0104-7
© Е. К. Годунова, 2012
© МПГУ, 2012
© Оформление. Издательство «Прометей», 2012
Стр.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