Проблема типовых элементов программирования

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

Область машиностроения наряду с такими "кубиками", как болты, гайки, оперирует множеством нетиповых элементов. Например, левое крыло и правое крыло автомобиля хотя и очень похожи друг на друга, но не могут быть взаимозаменяемыми и могут использоваться лишь в конкретной модели автомобиля.

Объектно-ориентированные языки программирования дали четыре новых механизма использования кубиков:

1) механизм классов, порождающих при выполнении любое количество однотипных объектов, например, ряд однотипных кнопок;

2) возможность тиражирования объектов от породившей программы во все новые программы;

3) динамически линкуемые библиотеки с порождающими объекты классами;

4) механизм сборки программ из "кубиков" — объектов в процессе их выполнения.

Таким образом, в теории программирования проблема "кубиков" остается важнейшей проблемой, поэтапное решение которой уже позволило создавать самые большие по количеству составных частей искусственные системы — программы. Второй аспект проблемы "кубиков" — удешевление программных разработок за счет повторного использования во всех новых программах частей, созданных в предшествующих разработках.

Определение графов

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

Ориентированный граф (орграф) – граф, у которого все ребра ориентированы, т.е. ребрам которого присвоено направление.

Неориентированный граф (неорграф) – граф, у которого все ребра не ориентированы, т.е. ребрам которого не задано направление.

Смешанный граф – граф, содержащий и ориентированные и неориентированные ребра.

Петлей называется ребро, соединяющее вершину саму с собой. Две вершины называются смежными, если существует соединяющее их ребро.

Простой граф – это граф, в котором нет ни петель, ни кратных ребер.

Мультиграф – это граф, у которого любые две вершины соединены более чем одним ребром.

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

Маршрут называется открытым, если его начальная и конечная вершины различны, в противном случае он называется замкнутым.

Маршрут называется цепью, если все его ребра различны. Открытая цепь называется путем, если все ее вершины различны.

Замкнутая цепь называется циклом, если различны все ее вершины, за исключением концевых.

Граф называется связным, если для любой пары вершин существует соединяющий их путь.

Вес вершины – рациональное число, поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.). Вес (длина) ребра – число или несколько чисел, которые интерпретируются по отношению к ребру как длина.

Взвешенный граф – граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).

4. Представление графов в компьютере: требования к представлению графов, матрица смежности, матрица инцидентности.

Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи.

 

Рис. 2. Пример графа

1. Список ребер – это множество, образованное парами смежных вершин (рис. 2). Для его хранения обычно используют одномерный массив размером m, содержащий список пар вершин, смежных с одним ребром графа. Список ребер более удобен для реализации различных алгоритмов на графах по сравнению с другими способами.

Рис. 3. Список рёбер графа

1. Матрица смежности – это двумерный массив размерности n x n, значения элементов которого характеризуются смежностью вершин графа (рис. 2). Значение элемента матрицы – вес ребра, которое соединяет соответствующие вершины. Данный способ действенен, когда надо проверять смежность или находить вес ребра по двум заданным вершинам.

Рис. 4. Матрица смежности графа

2. Матрица инцидентности – это двумерный массив размерности n x m, в котором указываются связи между инцидентными элементами графа (ребро и вершина). Столбцы матрицы соответствуют ребрам, строки – вершинам (рис. 5). Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром. Данный способ является самым емким для хранения, но облегчает нахождение циклов в графе.

Рис. 5. Матрица инцидентности графа