DRAKON.SU

Текущее время: Вторник, 19 Март, 2024 06:07

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
СообщениеДобавлено: Понедельник, 14 Октябрь, 2019 19:46 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5844
Откуда: Москва
В языке ДРАКОН пересечения запрещены

http://bit.ly/2MGB3bd
Цитата:
Минимальное число пересечений рёбер графа

Материал из Википедии — свободной энциклопедии

Рисунок графа Хивуда с тремя пересечениями. Это минимальное число пересечений среди всех возможных рисунков этого графа, так что число пересечений графа равно cr(G) = 3.

В теории графов число пересечений cr(G) графа G — это наименьшее число пересечений рёбер плоского рисунка графа G. Например, граф является планарным тогда и только тогда, когда его число пересечений равно нулю.

Математической отправной точкой изучения числа пересечений стала задача Турана о кирпичной фабрике, поставленная Палом Тураном, в которой требовалось найти число пересечений полного двудольного графа Km,n[1].

Однако та же самая задача поставлена в социологии примерно в то же самое время в связи с построением социограмм[2]. Задача продолжает играть большую роль в визуализации графов.

Если не указано другое, число пересечений относится к представлениям графов с помощью любых кривых. Условие прямолинейных пересечений требует, чтобы все рёбра были отрезками прямых, что может изменить ответ. В частности, число прямолинейных пересечений полного графа равно минимальному числу выпуклых четырёхугольников, определённых множеством n точек в общем положении, что тесно связано с задачей со счастливым концом[3].


Содержание

1 История
2 Сложность
3 Число пересечений кубических графов
4 Неравенство для числа пересечений
4.1 Доказательство неравенства для числа пересечений
5 См. также
6 Примечания
7 Литература

История

Во время Второй мировой войны венгерский математик Пал Туран вынужден работать на кирпичной фабрике, толкая тележку, гружёную кирпичами, от обжиговых печей в склады. На фабрике имелись колеи от каждой печи до каждого склада, и тележку труднее толкать в местах пересечения колей, что привело Турана к постановке задачи кирпичной фабрики: каково минимальное число пересечений рисунка полного графа?[4].

Заранкиевич (Zarankiewicz) пытался решить задачу Турана[5]. Его доказательство содержало ошибку, но он установил правильную верхнюю границу

Читать дальше


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

Часовой пояс: UTC + 3 часа


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

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


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

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2024, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB