В работе рассмотрены основные понятия теории графов, способы задания графов, структуры данных и особенности программирования на С задач на графах, заданных в табличной и списочной формах, программирование на С задач на графах, в том числе, определения вершины с наибольшей локальной степенью, нахождения паросочетания графа, разбиения графов на части, размещения мультиграфов в вершины ортогональной решетки.Предназначено для студентов очной формы обучения по направлению подготовки 09.03.02 «Информационные системы и технологии».

ВВЕДЕНИЕ......51. ОСНОВЫ ТЕОРИИ ГРАФОВ......71.1. Что такое граф......71.2. Симметрический граф и мультиграф......91.3. Граф – это универсальная модель......10Вопросы для самоконтроля......122. ПРЕДСТАВЛЕНИЕ ГРАФОВ И ПРОГРАММИРОВАНИЕ......132.1. Матрица смежности графа......132.2. Матрица инцидентности графа......152.3. Списочная форма задания графа......17Вопросы для самоконтроля......203. ПРОГРАММИРОВАНИЕ ЗАДАЧ НА ГРАФАХ......213.1. Определение локальной степени заданной вершины графа......213.2. Определение вершины с наибольшей локальной степенью......223.3. Определение вершин графа
смежных одновременно двум заданным вершинам графа......243.4. Определение вершин графа
смежных любой из двух заданных вершин графа......263.5. Определение паросочетания графа......264. РАЗБИЕНИЕ ГРАФА НА ПОДГРАФЫ......314.1. Постановка и практическое применение задачи разбиения графов на подграфы......314.2. Разбиение графа на части с использованием методов случайного разбиения......344.3. Определение числа ребер между любыми двумя заданными элементами......374.4. Подсчет числа связей между элементами
находящихся в двух разных заданных подмножествах......394.5. Случайное распределение заданного множества элементов на два подмножества......414.6. Окончательный вариант программы на С разбиения мультиграфа на два подграфа......494.7. Программа разбиения мультиграфа на две части с использованием функций......53Вопросы для самоконтроля......575. РАЗМЕЩЕНИЕ ВЕРШИН МУЛЬТИГРАФА В ГРАФ ОРТОГОНАЛЬНОЙ РЕШЕТКИ......595.1. Постановка задачи размещения вершин мультиграфа в граф ортогональной решетки......595.2. Методы размещения вершин мультиграфа в граф регулярной ортогональной решетки......625.3. Определение расстояния между двумя любыми вершинами графа ортогональной решетки......645.4. Определение длины ребер между двумя вершинами мультиграфа
размещенными в выбранные вершины графа ортогональной решетки......685.5. Определение длины ребер между вершинами мультиграфа при их размещении вершины графа ортогональной решетки......705.6. Случайное назначение вершин графа ортогональной решетки вершинам мультиграфа......735.7. Программирование общей задачи размещения вершин мультиграфа в вершины графа ортогональной решетки......75Вопросы для самоконтроля......80БИБЛИОГРАФИЧЕСКИЙ СПИСОК......82