Реферат: Отображение АСД на СДХ

- поиск символа,

- вставка символа,

- удаление символа,

- замена символа.

Граф

Графом гамма называются пары (X,U), где X - множество, U- отношение порядка на X (X - частично упорядоченное множество).

Если U - просто порядок, то граф - ориентирован, в силу свойства антисимметричности.

Если U - предпорядок, то граф неориентированный.

Пару (a,b) соединяют дугой, если пара (a,b) Î множеству U.

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

m: UÞR

Граф гамма - размеченный, если задано некоторое отображение

h: X Þ A, где A - множество меток.

ПРИМЕРЫ: 1) сеть дорог (вес - расстояние, метка - название населенного пункта). Найти кратчайший путь из п.A в п.B.

2) Найти электрические характеристики в различных участках электрической цепи.

Способы задания графа:

- графический,

- применение матрицы смежности

½x½ = n; X...X

.

X

ì 1, (X, X) Î U

S = í

î 0, (X, X) Ï U

- применение матрицы инцедентности

U...U (дуги)

X

.