Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Пример 4.1

Решение задач линейного программирования средствами табличного процессора Ехсеl | Анализ оптимального решения на чувствительность | Общая характеристика распределительной задачи | Транспортная задача | Поиск допустимого решения методом минимального элемента | Поиск оптимального решения. Метод потенциалов | Транспортные задачи с неправильным балансом | Транспортная задача с избытком запасов | Транспортная задача с избытком заявок | Вырожденное решение |


Читайте также:
  1. Fill in the missing numerals in the following sentences as in the example given for the first sentence. (Вставьте пропущенное имя числительное как в примере.)
  2. Gt; Часть ежегодно потребляемого основного напитала не должна ежегодно воз­мещаться в натуре. Например, Vu стойкости машины в течение года перенесена на
  3. IV. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ПРИМЕРНОЙ ПРОГРАММЫ
  4. IX. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К СЕМИНАРСКИМ ЗАНЯТИЯМ. ПРИМЕР.
  5. VII. Примерный перечень тем рефератов и курсовых работ
  6. Актуальный пример разработки программы в случае моббинга
  7. Анализ логопедического занятия (примерная схема протокола)

Пусть дан граф G (V, X),, изображенный на рис. 4.7. Справа от него дана соответствующая матрица инциденций.

Рис. 4.7 Граф и соответствующая ему матрица инциденций

 

Матрица инциденций определяет граф с точностью до изоморфизма, т.е. по матрице инциденций можно построить граф, в котором соответствующие вершины и ребра будут сохранять отношение смежности. С другой стороны, два графа изоморфны, если у них совпадают матрицы инциденций с точностью до перестановок строк и столбцов. В матрице инциденций связного графа любые p-1 строк однозначно определяют граф, так как недостающая строка есть их сумма по модулю 2. Ранг матрицы инциденций связного графа равен p-1.

Граф несвязен, если множество его вершин распадается на два (или более) непересекающихся подмножества, таких, что нет ни одного ребра, концы которого принадлежат разным подмножествам. Иными словами, несвязный граф состоит из двух и более частей, не соединенных ребрами.

Компонентой связности графа называется связный подграф, который не принадлежит ни одному большему связному подграфу. Если граф имеет несколько компонент связности, то при соответствующей нумерации вершин и ребер графа матрица инциденций имеет блочно-диагональный вид. При этом подматрицы на главной диагонали соответствуют компонентам связности графа.

Рис. 4.8 Все возможные абстрактные графы четвертого порядка

(несвязные: G1–G5; связные: G6–G11)

 

Элементы матрицы инциденций ориентированного графа определяются по формуле


Дата добавления: 2015-07-21; просмотров: 72 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Порядок выполнения работы| Пример 4.2

mybiblioteka.su - 2015-2024 год. (0.005 сек.)