Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Графы поиск цикла
СообщениеДобавлено: 16 апр 2015, 22:14 
Не в сети
Профи
Зарегистрирован:
01 янв 2014, 16:42
Сообщений: 374
Откуда: Минск
Cпасибо сказано: 21
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Добрый день , помогите пожалуйста найти цикл , чтобы найти цикл мы руководствовались статьёй
Изображение

Мы = ( группа, бригада) нарисовали граф ,визуально нашли циклы {0, 3} {3, 6} {6, 9} {8, 10} {7, 10} {4, 7} {4, 8} {1, 4}
Но методом " вычеркиванием вершин " у нас ничего не получилось. Обьясните пожалуйста ошибка в графе или в наших подсчетах.
▼ Статья
Цитата:
Можно. Обычным алгоритмом: вычеркиванием вершин которые имеют только входные или только выходные дуги. Допустим, у тебя есть список вершин:
1, 2, 3, 4, 5, 6, 7
, и список ребер:
{1, 6} {2, 1} {2, 3} {2, 4} {2, 6} {3, 4} {3, 5} {4, 5} {5, 3} {5, 6} {5, 7} {7, 1} {7, 6}


(вот такой граф имеется в виду, если что)
user posted image

Просматриваешь список ребер в поисках вершины, из которой не выходят ребра (если таковых нет - то ищешь вершину, в которую ребра не входят). Это #6, туда ребра только входящие, нет исходящих. Вычеркиваешь все ребра, которые содержат эту вершину. И саму вершину убираешь из списка:
1, 2, 3, 4, 5, 6, 7
{1, 6} {2, 1} {2, 3} {2, 4}{2, 6} {3, 4} {3, 5} {4, 5} {5, 3} {5, 6} {5, 7} {7, 1} {7, 6}

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

3, 4, 5
{3, 4} {3, 5} {4, 5} {5, 3}
Это и будет цикл...

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ 1 сообщение ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задачка с исследованием цикла

в форуме Молекулярная физика и Термодинамика

djeak11

0

425

16 мар 2017, 19:59

Алгоритм поиска цикла

в форуме Дискретная математика, Теория множеств и Логика

stalker2022

8

183

21 дек 2022, 13:32

Создание цикла в matlab

в форуме MATLAB

Malicv

0

428

05 дек 2015, 18:00

Объясните разбиение цикла на транспозиции

в форуме Дискретная математика, Теория множеств и Логика

LonelyGamer

4

439

06 окт 2015, 03:08

Найти функцию сложности цикла

в форуме Информатика и Компьютерные науки

Tag45

1

122

16 дек 2022, 22:19

Порядковый номер технологического цикла

в форуме Теория вероятностей

MathematicHell

5

627

30 окт 2015, 10:24

Программа по блок-схеме (два цикла)

в форуме MathCad

mazahaka567

0

412

15 май 2015, 20:14

Теорема Пуанкаре-Бендиксона существование цикла

в форуме Дифференциальные и Интегральные уравнения

stolyarrrov

1

402

12 май 2018, 20:46

Перебор точек используя три вложенных цикла

в форуме MathCad

George_Smith

1

303

24 ноя 2016, 10:08

Расчёт длительности производственного цикла партии деталей

в форуме Экономика и Финансы

Axwel

1

427

24 июн 2018, 13:35


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved