2020-07-12
121
1. Радиус графа, полученного после гомеоморфного сжатия исходного графа.
2. Диаметр графа после гомеоморфного сжатия исходного графа.
3. Двусвязанность графа.
4. Бихроматичность (двудольность) графа.
5. Число вершин, удаленных от заданной по кратчайшим маршрутам каждой из следующих длин: 1, 2, 3 и т.д., для каждой вершины.
6. Число вершин, удаленных от пары вершин по кратчайшим маршрутам каждой из следующих длин: 1, 2, 3 и т.д., для каждой пары вершин.
7. Число вершин, удаленных от заданного ребра (дуги) по кротчайшим маршрутам каждой из следующих длин: 1, 2, 3 и т.д., для каждого ребра.
8. Цикломатическое число графа после удаления в нем петель.
9. Число висящих вершин и сумма попарно кратчайших расстояний между ними.
10. Наибольшее число ребер (дуг), удаление которых оставляет граф связным.
11. Диаметр графа после удаления в нем висячих вершин.
12. Число центральных вершин графа после удаления в нем висячих вершин.
13. Набор чисел ребер (дуг) подграфов, получаемых поочередным удалением пар вершин.
|
|
|
14. Набор чисел ребер (дуг) подграфов, получаемых поочередным удалением троек вершин.
15. Число компонент сильной связности графа.
16. Радиус графа после удаления в нем висячих вершин.
17. Средний диаметр графа после удаления в нем висячих вершин.
18. Число вершин и ребер (дуг) в графе окрестности каждой пары вершин.
19. Число вершин и ребер (дуг) в графе замкнутой окрестности каждой пары вершин.
20. Число вершин и ребер (дуг) в графе замкнутой окрестности каждой тройки вершин.
8. Организация защиты курсовой работы
Защита курсовой работы проводится в форме доклада c презентацией, который должен длиться не более 5 минут и содержать постановку задачи, математическое решение, сведения о разработанном программном обеспечении, а также основные результаты расчетов и их анализ. После доклада студент должен ответить на вопросы комиссии. Не рекомендуется задавать вопросы по теоретическим аспектам, не имеющим принципиального значения.
Комиссия имеет право рекомендовать лучшие работы на конкурсы и научно-технические конференции, проводимые кафедрой, факультетом, университетом.
9. Пример
Постановка задачи
Используя технологию нисходящего проектирования, сравнить два неориентированных графа, представленных массивом последователей (FO - представление), на эквивалентность по диаметру графа. Вершин графа не более 20, число рёбер не более 50. Предусмотреть ввод данных с клавиатуры и из текстового файла.
Входные данные
Входные данные приведены в табл.2, входные формы изображены на рис. 18, входной формат текстового файла показан на рис. 19:
|
|
|
Таблица 2
| Номер п/п | Наименование | Тип | Диапазон | Назначение |
| 1 | n1 | Целый | 1<n1<=20 | Количество вершин 1-го графа |
| 2 | m1 | Целый | 1<m1<=50 | Количество ребер 1-го графа |
| 3 | Fo1={ fo1[i]} | Массив целых чисел | 0<=fo1[i]<=n1 1<=i<=2m1+n1 | Fo-представление 1-го графа |
| 4 | n2 | Целый | 0<n2<=20 | Количество вершин 2-го графа |
| 5 | m2 | Целый | 1<m2<=50 | Количество ребер 2-го графа |
| 6 | Fo2={ fo2[i]} | Массив целых чисел | 0<=fo2[i]<=n2 1<=i<=2m2+n2 | Fo-представление 2-го графа |
Входные формы
Рис. 18
