Метрические характеристики графа
Понятие и матричное представление графов. Ориентированные и неориентированные графы. Опеределение матрицы смежности. Маршруты, цепи, циклы и их свойства. Метрические характеристики графа. Применение теории графов в различных областях науки и техники.
Подобные документы
Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.
реферат, добавлен 27.11.2008Примеры решения задач по заданию графов. Определение основных характеристик графа: диаметра, радиуса, эксцентриситета каждой вершины. Вычисление вершинного и реберного хроматического числа. Упорядоченность матричным способом и построение функции.
контрольная работа, добавлен 05.07.2014Основополагающие понятия теории графов. Определение эквивалентности, порождаемое группой подстановок, и доказательство леммы Бернсайда о числе ее классов. Понятие перечня конфигурации и доказательство теоремы Пойа. Решение задачи о перечислении графов.
курсовая работа, добавлен 18.01.2014Общие сведения о фигурах, вычерчиваемых одним росчерком. Теория графов Эйлера, задача о мостах. Правила построения фигуры без отрыва карандаша от бумаги. Задача об эйлеровом пути, применение графов в жизни, быту, различных отраслях науки и техники.
реферат, добавлен 16.12.2011Свойства операций над множествами. Формулы алгебры высказываний. Функции алгебры логики. Существенные и фиктивные переменные. Проверка правильности рассуждений. Алгебра высказываний и релейно-контактные схемы. Способы задания графа. Матрицы для графов.
учебное пособие, добавлен 27.10.2013Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
курсовая работа, добавлен 18.01.2013Вид графов, используемых в теории электрических цепей, химии, вычислительной технике и в информатике. Основные свойства деревьев. Неориентированный граф. Алгоритм построения минимального каркаса. Обоснование алгоритма. Граф с нагруженными ребрами.
реферат, добавлен 11.11.2008Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа, добавлен 30.01.2012Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа, добавлен 17.05.2015Разработка и анализ топологической модели электронной схемы для полного диапазона частот. Определение передаточной схемной функции методом эквивалентных схем в матричной форме, а также методом сигнальных графов, используя сигнальный граф Мэзона.
контрольная работа, добавлен 11.04.2016Общая характеристика графов с нестандартными достижимостями, их применение. Особенности задания, представления и разработки алгоритмов решения задач на таких графах. Описание нового класса динамических графов, программной реализации полученных алгоритмов.
реферат, добавлен 22.11.2010- 37. Планарные графы
Сущностные характеристики плоского и планарного графа. Основные особенности формулы Эйлера и критерия Понтрягина-Куратовского, их доказательства. Общая характеристика двух критериев планарности. Сущность и значение процесса применения гамма-алгоритмов.
реферат, добавлен 25.12.2011 Сущность и основные понятия теории графов, примеры и сферы ее использования. Формирование следствий из данных теорий и примеры их приложений. Методы разрешения задачи о кратчайшем пути, о нахождении максимального потока. Графическое изображение задачи.
курсовая работа, добавлен 14.11.2009Элементы теории графов. Центры и периферийные вершины графов, их радиусы и диаметры. Максимальный поток транспортировки груза и поток минимальной стоимости. Пропускная способность пути. Анализ сетей Петри, их описание аналитическим и матричным способами.
задача, добавлен 28.08.2010Основополагающие понятия теории графов и теории групп. Определение эквивалентности, порождаемой группой подстановок, и доказательство леммы Бернсайда о числе классов такой эквивалентности. Сущность перечня конфигурации, доказательство теоремы Пойа.
курсовая работа, добавлен 20.05.2013- 41. Теория графов
Нахождение минимального пути от фиксированной до произвольной вершины графа с помощью алгоритма Дейкстры, рассмотрение основных принципов его работы. Описание блок-схемы алгоритма решения задачи. Проверка правильности работы разработанной программы.
курсовая работа, добавлен 19.09.2011 Основні положення теорії графов. Алгоритм розфарбування графу методом неявного перебору. Задання графу матрицею суміжності. Особливості програмної реалізації на мові Turbo Pascal алгоритму оптимального розфарбування вершин завантаженого з файлу графа.
курсовая работа, добавлен 15.06.2014Отношение Р и наличие стандартных свойств: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность. Графы и матрицы замыканий отношения Р. Таблица значений, граф и матрица функции f. Исследование М на линейность (полноту).
контрольная работа, добавлен 06.06.2011Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.
курсовая работа, добавлен 22.01.2016Понятие матрицы достижимости и связности. Операция удаления вершины из графа. Алгоритм выделения компонент сильной связности. Разработка и листинг программы на языке Turbo Pascal, осуществляющей вычисление матрицы достижимости по заданному алгоритму.
курсовая работа, добавлен 26.04.2011Разработка логико-формальной модели описания методики изготовления винных изделий. Разделение ингредиентов и продукции на множества. Исследование на рефлексивность, транзитивность, симметричность. Построение графа, матрицы смежности и инцидентности.
контрольная работа, добавлен 07.06.2010Методика решения задач высшей математики с помощью теории графов, ее сущность и порядок разрешения. Основная идея метода ветвей и границ, ее практическое применение к задаче. Разбиение множества маршрутов на подмножества и его графическое представление.
задача, добавлен 24.07.2009Понятия теории графов, их связность и задача о кратчайшей цепи. Программная реализация метода Дейкстры, его сравнение с методом простого перебора. Описание логики программного модуля. Примеры работы программы нахождения кратчайшей цепи в связном графе.
курсовая работа, добавлен 25.11.2011Сущность и содержание, основные понятия и критерии теории графов. Понятие и общее представление о задаче коммивояжера. Описание метода ветвей и границ, практическое применение. Пример использования данного метода ветвей для решения задачи коммивояжера.
контрольная работа, добавлен 07.06.2011- 50. Связность графов
Рассмотрение понятия и видов графов как совокупности непустого конечного множества элементов; условия их связанности. Доказательства существования замкнутых Эйлеровой, Гамильнотовой и бесконечной цепей. Ознакомление с элементарными свойствами деревьев.
курсовая работа, добавлен 10.02.2012