Длина максимального цикла частично ориентированного графа

@remag7 · Регистрация: 22.11.2018

Студворк — интернет-сервис помощи студентам

Дан частично ориентированный граф. Нужно найти цикломатическое число и длину максимального цикла
0, 0, 1, 1, 0, 0, 1
0, 0, 0, 1, 1, 0, 0
1, 0, 0, 1, 0, 1, 0
0, 0, 1, 0, 1, 0, 0
0, 0, 0, 0, 1, 0, 1
0, 0, 0, 0, 0, 0, 1
0, 1, 0, 0, 0, 1, 0
Есть картинка, но запрещено выкладывать...

@3D Homer · 12.05.2019, 20:05

Сообщение от remag7

Дан частично ориентированный граф.

Чем он отличается от полностью ориентированного?

Сообщение от remag7

Нужно найти цикломатическое число и длину максимального цикла

Напомните, пожалуйста, определение цикломатического числа орграфа. Это размер наименьшего разрезающего циклы набора дуг?

@remag7 · 12.05.2019, 22:40 **[ТС]**

В частично ориентированном есть дуги и рёбра. То есть между некоторыми вершинами можно ходить вперёд и обратно, а в некоторых только в одну сторону. Цикломатическое число - число которое показывает кол-во циклов в неориентированном графе без петель и кол-во рёбер, которые нужно убрать, чтобы разорвать все циклы.

@3D Homer · 12.05.2019, 22:44

Сообщение от remag7

В частично ориентированном есть дуги и рёбра. То есть между некоторыми вершинами можно ходить вперёд и обратно, а в некоторых только в одну сторону.

Но ребра можно понимать как две дуги в обе стороны. И по матрице смежности восстанавливается именно такой орграф.

Сообщение от remag7

Цикломатическое число - число которое показывает кол-во циклов в неориентированном графе без петель и кол-во рёбер, которые нужно убрать, чтобы разорвать все циклы.

Как это число показывает обе характеристики: кол-во циклов и кол-во рёбер, которые нужно убрать? Какое определение этого понятия? Кроме того, я специально спрашивал вас про цикломатическое число орграфа.

@remag7 · 12.05.2019, 23:01 **[ТС]**

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

Добавлено через 42 секунды
Ну так дуга же не ребро
Вообще полное задание такое: определить характеристики графа (связность, число компонент связности, длина максимального цикла, эйлерова характеристика). Граф связный, число компонент связности 1, эйлерова характеристика 2. А вот длину я не знаю как считать.

Добавлено через 6 минут
Так цикломатическое число подходит для любого связного графа.

@3D Homer · 13.05.2019, 00:19

Сообщение от remag7

Ну так дуга же не ребро

Почему нельзя рассматривать циклы в орграфе, где вместо ребер рассматриваются две дуги? Разве циклы будут другими? Зачем вводить новое понятие (частично ориентированный граф), если с точки зрения данной задачи оно легко сводится к стандартному понятию? Аналогично я могу ввести понятие "трехконечного" ребра (u, v, w), которое на самом деле представляет собой вершину x и ребра (x, u), (x, v) и (x, w), и рассматривать графы с двумя типами ребер.

Минимальное множество ребер, которые нужно убрать для удаления циклов, есть (3, 1), (3, 4), (5, 7), (6, 7), (5, 5).

Наибольшие простые циклы (то есть без повторяющихся вершин, кроме первой и последней) есть 1, 7, 2, 4, 3, 1 и 2, 4, 3, 6, 7, 2.

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

@remag7 1 / 1 / 0 Регистрация: 22.11.2018 Сообщений: 206

	Длина максимального цикла частично ориентированного графа 12.05.2019, 13:20. Показов 2525. Ответов 5 Метки нет (Все метки) Дан частично ориентированный граф. Нужно найти цикломатическое число и длину максимального цикла 0, 0, 1, 1, 0, 0, 1 0, 0, 0, 1, 1, 0, 0 1, 0, 0, 1, 0, 1, 0 0, 0, 1, 0, 1, 0, 0 0, 0, 0, 0, 1, 0, 1 0, 0, 0, 0, 0, 0, 1 0, 1, 0, 0, 0, 1, 0 Есть картинка, но запрещено выкладывать... 0

@remag7 1 / 1 / 0 Регистрация: 22.11.2018 Сообщений: 206
	12.05.2019, 22:40 [ТС]
	В частично ориентированном есть дуги и рёбра. То есть между некоторыми вершинами можно ходить вперёд и обратно, а в некоторых только в одну сторону. Цикломатическое число - число которое показывает кол-во циклов в неориентированном графе без петель и кол-во рёбер, которые нужно убрать, чтобы разорвать все циклы. 0

@remag7 1 / 1 / 0 Регистрация: 22.11.2018 Сообщений: 206
	12.05.2019, 23:01 [ТС]
	Цикломатическое число графа указывает то наименьшее число рёбер, которое нужно удалить из данного графа, чтобы получить дерево (для связного графа) или лес (для несвязного графа), т.е. добиться отсутствия у графа циклов. Цикломатическое число мультиграфа равно максимальному числу независимых циклов. Вот такое в интернете написано Добавлено через 42 секунды Ну так дуга же не ребро Вообще полное задание такое: определить характеристики графа (связность, число компонент связности, длина максимального цикла, эйлерова характеристика). Граф связный, число компонент связности 1, эйлерова характеристика 2. А вот длину я не знаю как считать. Добавлено через 6 минут Так цикломатическое число подходит для любого связного графа. 0

Длина максимального цикла частично ориентированного графа

Решение