Несколько замечаний перед тем, как приступить к выполнению задания...

Задание

1)    Изучите теорию по теме "Графы"... смотри здесь

2)    Задача1. Составить программу, которая содержит процедуру создания заданного способа представления графа в памяти ЭВМ. Информацию о графах сохраните в текстовых файлах в своем разделе.

Предполагается, что вершины графа пронумерованы от 1 до N, а ребра – от 1 до M. Каждому ребру и каждой вершине может быть сопоставлен вес – целое положительное число.

Реализуйте в виде методов следующие  операции:

проверка смежности вершин v и w;
перечисление всех вершин смежных с v;
определение веса ребра (v, w);
определение веса вершины v;
перечисление всех ребер (v, w);
перечисление ребер, инцидентных вершине v;
перечисление вершин, инцидентных ребру s.

Варианты задания.
Варианты отличаются способом представления графа в памяти ЭВМ. Для конкретного студента вариант  определяется преподавателем. 

1)Матрица смежности.
2)Матрица инцидентности.
3)Списки смежных вершин. 
4)Перечень ребер.

Протестируйте свою задачу на конкретных графах:

Граф 1. Неориентированный граф.
   

Граф 2. Ориентированный граф.

3)    Задача 2. Задано бинарное дерево поиска (реализация на основе динамических списков). Необходимо реализовать процедуру добавления и удаления узла дерева, поиск заданного значения, а также реализовать прямой, обратный и концевой обходы дерева. Реализовать в программе проверку всех подпрограмм: добавление узлов (8-10 значений), все виды обхода получившегося дерева, поиск заданного значения, удаление заданного значения, все виды обхода получившегося дерева.

4)    Задача 3. Для заданной последовательности чисел, записанных в строку через пробел во входной текстовый файл, создать бинарное дерево поиска (реализация на основе массива). Запросить число с клавиатуры и воспользовавшись свойствами бинарного дерева поиска ответить на вопрос: есть ли заданное число в последовательности. В случае положительного ответа - удалить этот элемент из дерева. Провести прямой, обратный и внутренний обход дерева.
Указание: массив содержит n элементов, корень - 0-ой элемент, у каждой i-ой вершины есть два потомка: (2i+1)-ая и (2i+2)-ая вершины.

Контрольные вопросы и задания

1. Что такое ориентированный граф?
2. Что такое неориентированный граф?
3. Что такое дерево?
4. Что такое бинарное дерево поиска?
5. Какие есть способы представления ориентированного и неориентированного графа? Расскажите смысл некоторых из них?
6. Что такое смежные вершины в ориентированном и в неориентированном графе?
7. Что такое инцидентность?
8. Какие алгоритмы поиска в графе вы знаете?
9. Какие алгоритмы обхода дерева вы знаете?
10. Расскажите алгоритм вставки нового элемента в дерево поиска?
11. Расскажите алгоритм удаления элемента из дерева поиска?