рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Образование
- /
- Маршруты, цепи, циклы
Реферат Курсовая Конспект
Маршруты, цепи, циклы
Маршруты, цепи, циклы - раздел Образование, ...
39.Ориентированные графы. Диаграмма Графа. Матрицы смежности, инциденцией и достижимости.
Ориентированные графы - если условие f(vi, vj) = f(vi, vj) не задано и все элементы множества U изображаются дугами, то граф G называют ориентированным графом, или орграфом,
Диаграмма графа - графы принято изображать диаграммами, состоящими из кружков и линий. Кружки соответствуют вершинам графа. Линии, соединяющие кружки, соотвествуют ребрам графа.Внутри кружка пишется обозначение вершины.
Матрица смежности 
матрица А называется матрицей смежности графа G. Это симметрическая матрица с нулями на диагонали, число единиц в строке равно степени соответствующей вершины, т.е числу инцидентных этой вершине ребер.
Матрица инцидентности 
Матрица называется матрицей инцидентности графа G называется матрица с р строками (каждая строка соответствует одной из вершин графа) и q столбцами (каждый столбец соответствует одному из ребер графа),
Изоморфизм графов.
Графы называют изомрфными, если между множествами вершин можно установить взаимно однозначное соответствие, сохраняющее смежность. Отношение изоморфизма - отношение эквивалентности. Фактически, изоморфные графы - это один и тот же граф.
Маршруты, цепи, циклы.
пример маршрута: 1-2-3-5-7-4-3-5-6-2-3 пример замкнутого маршрута : 3-4-5-7-3-4-1-3Разрезы.
пусть G (V U) - неориентированный граф
Разрезом называется всякое множество R ребер графа G такое, что удаление этих ребер из графа делает его несвязным.
Разрез называется ппростым, если никакое его собственное подмножество разрезом не является. Разрез по-другому называют коциклом.
– Конец работы –
Используемые теги: маршруты, цепи, циклы0.06
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Маршруты, цепи, циклы
Что будем делать с полученным материалом:
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.12 сек.
Новости и инфо для студентов