С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
moonblade
0 / 0 / 0
Регистрация: 15.11.2010
Сообщений: 12
#1

Анализ графа - C++

15.11.2010, 13:41. Просмотров 465. Ответов 0
Метки нет (Все метки)

Задача:
Граф задaн мaтрицей инциденций. Определить является ли он aнтисимметрическим или полным aнтисимметрическим. Достроить до полного aнтисимметрического грaфа, если он тaковым не является. 6<n<10.
Мое понимание задачи:
Нужно задать матрицу N x M , состоящую из элементов [0,1,-1]. Каждый столбец может содержать только три варианта элементов (первый:одну 1 и одну -1, остальные нули, второй: одна 1, остальные нули, третий: одна -1, остальные нули). Т.к элементы вводятся вручную нужно поставить проверку: - на корректность ввода
После заполнения матрицы делаем проверку условий:
1)Если в каждом столбце есть одна 1 и одна -1,
2)Если нет одинаковых столбцов (расположение 1и -1 в каждом новом столбце должно быть отлично от предыдущих).Примечание: Столбцы различные только по знаку “-“ перед еденицей также считаются недопустимыми.
Если эти 2 условия выполняются:
выводим сообщение “Граф является антисимметрическим”, в противном случае выводим: “Граф не является антисимметрическим”.
Далее если условие выполняется(граф антисимметрический), делаем проверку в каждой строке на суммарное количество 1 и -1 ,оно должно быть N-1 .
Если суммарное кол-во 1 и -1 равно N-1, выводим готовую матрицу и сообщение: “Граф является полным антисимметрическим”.Если суммарное кол-во 1и -1 не равно N-1, добавляем новый столбец по следующему алгоритму:
Проверяем первую строку. Если в ней кол-во 1 и -1 не равно N-1 ,добавляем 1.Идем во вторую строку, если в ней кол-во 1 и -1 равно N-1 то добавляем ноль и переходим к след. строке. Если в ней кол-во 1 и -1 не равно N-1 , добавляем -1 ,в остальных строках ставим нули. Полученный столбец сравниваем с предыдущими по условию 2).Если условие выполняется, сохраняем столбец. Если не выполняется, то перезаписываем последнюю еденицу в столбце т.е. вместо -1 ставим 0 и проверяем след. строку итд пока не получим столбец удовлетворяющий условию 2) … И.т.д. пока в каждой строке суммарное кол-во 1 и -1 не будет равно N-1.
Кто поможет написать код? В долгу не останусь.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.11.2010, 13:41
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Анализ графа (C++):

заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь - C++
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь. Помогите написать...

Конденсация графа - C++
Найти число компонент сильной связности, вот может быть кто-нибудь реализовывал нечто подобное?

Подобие графа - C++
Имеется примерно такой вот класс: class Room { private: string name; string story; vector &lt;Room*&gt; rooms; //указатели,...

Периферия графа - C++
Ребят, есть у кого код на нахождение периферии графа?

Построение графа - C++
Вершины и ребра графа назовем его элементами. По графу G построить граф T(G), у которого в качестве вершин взяты элементы G, а две вершины...

построение графа - C++
Задача: &quot;Задан граф дерево с корневой вершиной. Нужно, начиная с корневой вершины, обойти все концевые вершины (концевая вершина имеет...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2010, 13:41
Привет! Вот еще темы с ответами:

Визуализация графа - C++
Есть произвольный граф, состоящий из набора узлов и связей между ними. Узлы представляются прямоугольниками с известной шириной и высотой,...

Построение графа - C++
Помогите пожалуйста написать программу вот задание:Построить копию заданного графа. граф произвольный на ваш выбор. Добавлено через...

Центр графа - C++
Дана матрица смежности. Найти максимальное расстояние в графе. Пол дня уже мучаюсь, искал в гугле, сам пытался, но ничего не...

МАТРИЦА РАССТОЯНИЙ ГРАФА - C++
Доброго времени суток! Помогите пожалуйста! Пытаюсь написать программу, которая находила бы матрицу расстояний по матрице смежности....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.