ВУЗ:
Составители:
Рубрика:
11
называемые весами. В простейшем случае это может быть порядковая нумерация
ребер и дуг, указывающая на очередность при их рассмотрении. Вес ребра (дуги)
может означать длину (пути сообщения), пропускную способность (линии связи),
напряжение или ток (электрической цепи), количество набранных очков (турниры),
валентность связей (химические формулы), количество рядов движения
(автомобильные дороги), цвет проводника (монтажная
схема электронного
устройства) и т.п.
Вес можно приписывать не только ребрам и дугам, но и вершинам. Вес
вершины может означать любую характеристику соответствующего ей объекта.
Например, количество мест в кемпингах, пропускной способностью станций
техобслуживания на карте автомобильных дорог, атомный вес элемента в
структурной формуле, цвет изображаемого вершиной предмета, возраст
человека и
т.п.
Особое значение для моделирования физических систем имеют взвешенные
ориентированные графы, названные графами потоков сигналов или
сигнальными
графами. Вершины сигнального графа отождествляются с некоторыми
переменными, характеризующими состояние системы, а вес каждой вершины
означает функцию времени или некоторые величины, характеризующие
соответствующую переменную (сигнал вершины). Дуги отображают связи между
переменными, и вес каждой дуги представляет собой численное или
функциональное отношение, характеризующее передачу сигнала от одной вершины
к другой. Сигнальные графы
находят широкое применение в теории цепей и систем,
а также во многих других областях науки и техники.
Подграфы
Граф Н называется подграфом (или частью) графа G, если вес его вершины и
ребра принадлежит G: VH
⊆
VG, ЕH
⊆
ЕG. Если Н – подграф графа G, то говорят,
что Н содержится в G. Подграф Н называется остовным подграфом (или
фактором), если он содержит все вершины G: VH=VG. Если множество вершин
подграфа Н есть U, а множество его ребер совпадает с множеством всех ребер графа
G, оба конца которых принадлежат U, то Н называется
подграфом, порожденным
(или
индуцированным) множеством U, и обозначается через G(U). На рис. 14
изображен граф G и три его подграфа Н
1
, Н
2
и Н
3
, среди которых Н
3
является
остовным, а Н
2
– порожденным.
Рис. 14
Важный класс подграфов составляют подграфы, полученные в результате
удаления вершин. Пусть v – вершина графа G. Граф G
v
=G-v получается из графа G
в результате удаления вершины v и всех инцидентных ей ребер. Очевидно, что
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
