Граф и отношения делимости

Построим граф, изображающий отношение делимости на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на 2.

Подграфы

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

Подграф, порожденный множеством вершин U – это подграф, множество вершин которого - U содержащий те и только те ребра, оба конца которых входят в U.

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Связность графа

Граф называется связным, если любая пара его вершин связана.
Связными компонентами графа называются подграфы данного графа, вершины которых связаны.

Деревья

Дерево — это связный граф без циклов.
Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярны генеалогические деревья.

Лес – это граф без цикла. Вершины степени 1 в дереве называются листьями.
Деревья отличаются от простых графов тем, что при обходе дереваневозможны циклы, и э то делает графы очень удобной формой организации данных для различных алгоритмов. Таким образом, понятия дерева активно используется в информатике и программировании.

В теории графов применяются:

1. Матрица инцинденций - это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующих рёбрам.

2. Матрица смежности - это матрица n×n где n - число вершин, где b_ij = 1, если существует ребро, идещее из вершины х в вершину у и b_ij = 0 в противном случае.

Список литературы

http://matmetod-popova.narod.ru/theme213.htm

http://www.algolib.narod.ru/Graph/Base.html

http://lib.vvsu.ru/books/Bakalavr01/page0221.asp

http://dmtsoft.ru/bn/391/as/oneaticleshablon/

Не нашли, что искали? Воспользуйтесь поиском: