Программа построения графа путем замены вершин в исходном графе на ребра, страница 2

name_r Name,otvet;

char isk[2];

clrscr();

f=fopen ("input.txt","r");

if (f==NULL) printf ("Файл ввода input.txt ненайден");

else

{

include (f,&T,&name);

rebra (&Name,T,&name);

printf ("Таблица инцидентности графа G\n");

print_table (T,name);

R=rebra_inc (Name);

printf ("\nТаблица инцидентности графа G'");

print_table_R (R,Name);

printf ("\nВведите искомую вершину ");

scanf ("\n%c",&isk[0]);

scanf ("\n%c",&isk[1]);

otvet=otv(R,Name,isk);

if (otvet.N==0) printf ("Ответ: Вершины ненайдены.");

else {printf ("Искомые вершины\n");

print_reb (otvet);

}

}

getch();

}

7. Набор тестов

Исходные данные	Результат
Файл input.txt: abcdefghi 010001101 101110000 010000000 010000000 010000000 100000010 100000000 000001000 100000000 Искомая вершина: bc	Искомые вершины: af ag ai bd be ab
Файл input.txt: abcdefghi 010001101 101110000 010000000 010000000 010000000 100000010 100000000 000001000 100000000 Искомая вершина: hf	Искомые вершины: ab ag ai

Файл input.txt: abcdefghi 010001101 101110000 010000000 010000000 010000000 100000010 100000000 000001000 100000000 Искомая вершина: nm	Такой вершины не существует Ответ: Вершины не найдены
Файл input1.txt: abc 010 101 010 Искомая вершина: ba	Ответ: Вершины не найдены

1.Условие задачи

По графу G построить граф G’ следующим образом: в качестве вершин в G’ берутся ребра графа G: две вершины в G’ смежны тогда и только тогда, когда смежны соответствующее ребра. В G’ найти все вершины расстояние от которых до некоторой выделенной равно 2.

2.Анализ задачи

Дано: вершины, таблица инцидентности графа G, вершина поиска

Результат: Сначала на экран выводится таблица инцидентности графа G потом G’, искомые вершины или сообщение о том, что таких нет.

Метод решения:

1.  Составим таблицу инцидентность графа G’

Если две вершины A и B графа G смежны значит существует такая вершина AB графа G’. Смежность вершин A и B легко определит по таблице инцидентности графа G. Затем найдя все вершины G’ сравним их попарно, если в названии двух вершин существуют равные символы, то это вершины смежны.

2.  Найдем необходимые вершины

Найдем все вершины смежные с вершиной поиска и запомним их (промежуточные вершины поиска). Удалим из таблицы инцидентности G’ все данные о вершине поиска. Далее найдем все вершины смежные с промежуточными и запомним их первые вхождения. Это и будут искомые вершины.

3.Используемые функции и их прототипы

void include (FILE *f,table_inc *T,vershin *name) - Функция ввода

void rebra (name_r *Name,table_inc T,vershin *name) - Функция перевода ребер в вершины (графа G в граф G')

table_inc rebra_inc (name_r Name) - Функция таблицы инцидентности для ребер

void print_table (table_inc T,vershin name) – Функция вывода таблицы инцидентности G

void print_table_R (table_inc R,name_r Name) – Функция вывода таблицы инцидентности G’

int search_reb (name_r Name,char isk[2]) - Функция поиска ребра в списке имен ребер и выводит порядковый номер ребра

name_r delete_reb (table_inc *R,name_r *Name,int k) - Функция удаления ребра из таблицы инцидентности

name_r otv (table_inc R,name_r Name,char isk[2]) – Функция поиска искомых вершин в G’

void print_reb (name_r Name) - Функция печатающая ответ

4. Структура данных

typedef struct name_r {char reb[n][2];int N;}; - Структура хранящая ребра

typedef struct vershin {char ver[n];int N;}; - Структура хранящая вершины

typedef struct table_inc {int znach[n][n]; int N;}; - Структура хранящая таблицу инцидентности

5. Алгоритм решения