DRAKON.SU

На форуме оживилась тема про школу Шалыто. В тех краях есть такая любопытная штуковина:

Так называемые линейные бинарные графы также планарны, как и ДРАКОН. Применяются не только для отображения структур логических формул, но и имеется методика построения общей схемы для "склеивания" нескольких формул, для чего и необходимо раскладывать явно "да/нет"-отношения.
В общем, это пример полезности такой возможности.

Схемы выражаются и по-драконовски.

Данилов В.Р. Методы представления функции переходов при генерации автоматов управления на основе генетического программирования

Рис. 21. Линейные бинарные графы для формул на переходах

У графа Шалыто есть интересное преимущество: он компактный и линейный.

линейные бинарные графы

Кому это надо?
Где это используется?

Есть практические примеры? Без абстрактных: a, b, c, f.
Смысла в приведенных графах нет.

Методы представления функции переходов при генерации автоматов управления на основе генетического программирования

Path graph
From Wikipedia, the free encyclopedia
(Redirected from Linear graph)

In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order v1, v2, …, vn such that the edges are {vi, vi+1} where i = 1, 2, …, n − 1. Equivalently, a path with at least two vertices is connected and has two terminal vertices (vertices that have degree 1), while all others (if any) have degree 2.

Paths are often important in their role as subgraphs of other graphs, in which case they are called paths in that graph. A path is a particularly simple example of a tree, and in fact the paths are exactly the trees in which no vertex has degree 3 or more. A disjoint union of paths is called a linear forest.

Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts.

Перевод на русский

математической области теории графов , А путь графа или линейный граф представляет собой график , чьи вершины могут быть перечислены в следующем порядке : V 1 , об 2 , ..., v п такие , что ребра являются { об я , v я + 1 } , где i = 1, 2,…, n - 1. Эквивалентно, путь, по крайней мере, с двумя вершинами связан и имеет две конечные вершины (вершины, имеющие степень 1), в то время как все остальные (если таковые имеются) имеют степень 2.

Пути часто играют важную роль в качестве подграфов других графов, и в этом случае их называют путями в этом графе. Путь является особенно простым примером дерева , и на самом деле пути - это именно те деревья, в которых ни одна вершина не имеет степени 3 или более. Объединение непересекающихся путей называется линейным лесом .

Пути - это фундаментальные понятия теории графов, описанные во вводных разделах большинства текстов по теории графов.

Линейные бинарные графы

сегодня, 22:49

Здравствуйте, Владимир Рюрикович!

Прочитал Вашу работу МЕТОД ПРЕДСТАВЛЕНИЯ АВТОМАТОВ ЛИНЕЙНЫМИ БИНАРНЫМИ ГРАФАМИ ДЛЯ ИСПОЛЬЗОВАНИЯ В ГЕНЕТИЧЕСКОМ ПРОГРАММИРОВАНИИ
Меня заинтересовали линейные бинарные графы.

Я сравнил их с представлением на языке ДРАКОН в теме:
Язык ДРАКОН и линейные бинарные графы

Обращаюсь к Вам с просьбой: если Вас не очень затруднит, высказать Ваше мнение

С уважением,
Владимир Данилович Паронджанов
Mobile: +7-916-111-91-57
Viber: +7-916-111-91-57
E-mail: vdp2007@bk.ru
Skype: vdp2007@bk.ru
Website: http://drakon.su
Webforum: http://forum.drakon.su

Re: Линейные бинарные графы

сегодня, 16:07

Добрый день,

Прошу прощения за поздний ответ. Насколько я понял, эти графы можно перерисовать в форму языка ДРАКОН, с сохранением их свойств, но это понятно и без меня

Насчёт преимуществ одного над другим - насколько я помню, линейные бинарные графы использовались профессором Шалыто в схемотехнике, где важна планарность (возможно линейность тоже даёт некие преимущества, тут я точно не знаю).

В нашей с ним работе это представление использовалось для генетических алгоритмов (преимущество тут в компактности по сравнению с полной таблицей). Не знаю, в какой работе Шалыто они упоминаются в первый раз, я ссылался на Шалыто А.А. "Логическое управление. Методы аппаратной и программной реализации алгоритмов".

Возможно, там преимущества представления описаны подробнее, но сейчас книги у меня нет.

Надеюсь, что смог хоть чем-то тут помочь.

С уважением,
Владимир