Форум программистов, компьютерный форум CyberForum.ru

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

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

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

15.11.2010, 13:41. Просмотров 448. Ответов 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.
Кто поможет написать код? В долгу не останусь.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.11.2010, 13:41     Анализ графа
Посмотрите здесь:

Фундоментальные циклы графа - C++
Нужна программа на C\C++.по фундоментальным циклам графа,есть прога подобная на паскале но она у меня почемуто не работает...хотя пример...

K-связность неориентированного графа - C++
Ребят, третью неделю уже думаю, не могу решить. Нужно написать программу на с++, определяющую k-связность графа. Как я понял с...

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

поиск центра графа - C++
Здраствуйте. нужен универсальный код поиска центра графа(вершины или двух). рисовать или вставлять граф не нужно.

Построение ориентированного графа - C++
Привет!) Покажу код, то что я делал. На выходе нету расстояний(стоимости). Как добавить расстояние на графе. #include...

Проверка на связанность графа - C++
Всем Привет. Я получил задание проверить связанный ли граф , у меня имеется матрица смежности (adjacency matri) ,а также написаны и...

Удаление вершины графа - C++
Добрый вечер. Нужна помощь в удалении вершины графа. Вот код: struct arc; struct node { int id; ...

Хранения Графа в памяти - C++
Вечер добрый. Есть графы.В них: Точки, рёбра, длины рёбер, координаты точек, точки не имеющие соединения рёбрами, точки в которые или из...

Хроматическое число графа - C++
Здравствуйте =) Не можете подсказать какой-либо алгоритм нахождения хроматического числа графа

Обход в ширину графа - C++
Здравствуйте, помогите пожалуйста разобраться что не так в алгоритме работы обхода в ширину графа( Заданию матрицу Число вершин ...

Варианты обхода графа - C++
подскажите пожалуйста сколько путей существует для такого графа, чтобы проходить через каждую Добавлено через 44 секунды или...

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


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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