Часто в типовых решениях, например, в БП в закрытии месяца используются основы и формулы теории графов. Т.к. я не математик, то многое не понятно. Где можно ознакомиться с теорией и формулами в минимальном объеме,чтобы понимать суть алгоритма? Кто нибудь использует ещё основы теории графов в своих разработках?

В вуз сходить не предлагать? ))))
И там не графы, насколько я помню...

(1) не было в вузе теории графов.

Ну там в алгоритме пишут:вершины, ребра и т.д. а что это ещё?

(2) Там скорее всего конкретный алгоритм(ы) их и изучай.

Для основ хватит https://ru.wikipedia.org/wiki/Теория_графов

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

(0) http://graphcost.com/index.php/2014-04-03-11-51-41/102-grafy-zatrat-modelirovanie-v-mikroekonomike

https://stepik.org/course/5608

(0) Было дело, УПП-шную ИНВ-19 делал (см. 13 пост в Пересортица по товарам. Как лучше закрыть? )

(2) у меня в курсе дискретной математики было. Не очень много, но азы давали. Рекомендую качнуть книжку Витольд Липский, Комбинаторика для программистов. Там кое-что есть для общего развития по теме.

(0) очень редко, но использую стандартные алгоритмы. Но это нетиповые для 1сника задачи, имхо.

(0) никогда

мозг не тянет такие вычисления

(2) У нас было. Может, надо было не в сельхозе учиться, а на программиста?

(0) нет там ничего сложного. На ютубе 5 минутных роликов полно - практически по каждому вопросу - с анимацией и понятными объяснениями.

(11) обожаю когда кто то говорит надо-было))) Надо было ставить на зеро)))

(10) там нет никаких бешеных вычислений. Достаточно простые вещи. Матрицы смежности, инцидентности, списки инцидентности, алгоритмы нахождения разного рода путей... До сих пор что-то помню, хотя последний раз игрался с этим в вузе...

это где в БП юзается теория графов?

(15) Закрытие месяца, раскидывание косвенных затрат.

(16) КЗ на себестоимость выпущенной продукции

и что там из теории графов используется?

(14) просто мозг у всех разный...

(0,2)  У тебя просто специальность не относилась, видимо к программированию или экономике.
Все кафедры ПМ, ММ и мат.экономики теорию графов изучают в обязательном порядке.
Ничего там сложного нет, в 1С азы используются.

(11) даже если не было этого в ВУЗе - что мешает сделать это сейчас? риторический вопрос, конечно...

(20) "Все кафедры ПМ, ММ и мат.экономики теорию графов изучают в обязательном порядке." - сейчас, похоже, уже нет.
сын учится на приме - у них курс математики (на энтом самом блякалявриате) такой же, как был у нас 35 лет назад на чисто инженерной (правда, немного усиленной) специальности.

+(21)
https://openedu.ru/course/#query=теория%20графов
https://stepik.org/catalog?q=Теория%20графов

(18)
ОЦЕНКА ЗАТРАТ.
Для того, чтобы оценить затраты, представим их движение в виде графа.

Граф состоит из ребер и вершин.
Вершины - это состояния _затрат_, например, "20 счет по конкретному подразделению, НГ и статье затрат", или "41 счет, конкретное наименование товара, конкретный склад, конкретная партия".
Важно: объекты учета, не являющиеся затратами, не входят в число вершин.
Например, не будет вершины, соответствующей счету 90.02.

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

Ребра - это движение затрат внутри учета затрат. Например - выпуск продукции или перемещение товаров, но не реализация услуг.
В начале работы процедуры.
- суммовой оценки не имеют.
- вес вершины - это количественная характеристика движения.
По окончании работы процедуры.
- назначается суммовая оценка ребер.
- вес не меняется.

Движения по распределению расходов - это также ребра.
Для них вес - это коэффициент распределения.

Алгоритм оценки основан на допущении: игнорируются, разрушаются замкнутые маршруты в графе - "циклы", контуры (далее используем термин "Контур", чтобы не путаться с ключевым словом языка Цикл).

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

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

Для вершин разных типов (Запасов и Расходов) и ребер разных типов (Перемещений, Распределений) применяются разные методы разрушения контуров.
1. Для перемещений считаем, что если товар в ходе перемещений снова попал в исходное состояние, то он как бы не перемещался, это движение можно исключить из общего оборота, а стоимость движения принять равной 0.
2. Для остальных движений внутри контура запасов ("комплектаций") просто игнорируем одно из ребер цикла (считаем, что циклы в комплектациях редки, поэтому допустимо пожертвовать точностью вычислений за счет простоты алгоритма).
3. Контуры, которые проходят через вершины типа "Расходы", называются встречным выпуском.
Для таких контуров применяем следующий подход:
- заранее находим контуры и находим "слабые звенья" в них - те, которые потом разомкнем, тем самым разрушив цикл.
- в ряде алгоритмов игнорируем "слабые звенья", но полностью циклы не разрушаются.
- оценку расходов выполняем дважды:
- сначала оцениваем весь граф, включая "слабые звенья".
- затем разрушаем контуры, зафиксировав оценку слабых звеньев, полученную при первом распределении.
- наконец, выполняем оценку еще раз, начиная с тех вершин, в которые вели слабые звенья.

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

(22) я экономист. Было экономико математическое моделирование. Но там отдельные задачи проходили: задача коммивояжера, задача о грибах и ТД. Это и есть теория графов?

(24) это реально используется, или это выдержки из книги Полякова?

(26) Реально

(25) Что такое "задача о грибах"? Такой не слышал, интересно, что за зверь.

(28) "Имеется 100 кг грибов влажностью 99%. Влажность уменьшилась на 1%. Сколько теперь весят грибы? "

(24) А что, СЛАУ уже отменили?

50 кг, что ли? x*2 = 100*1
Непонятно, при чем здесь теория графов?

(0) Это называется дискретная математика. Учебников по ней валом.

(14) у меня в универе было 7 разных математик

везде сдал на 4+

просто практики с тех пор вообще нет - сейчас уже ничего не вспомню

() > Часто в типовых решениях, например, в БП в закрытии месяца используются основы и формулы теории графов.

Вряд ли! Там в теории графов (ТГ) нет ни малейшей необходимости, разве, что для понтов только. Тип, вот мы тебе нарисовали графическую схему, для чего использовали ТГ. Еще раз, «это всё от балды дверца».

Кстати, формул ТГ, как таковых тоже нет. Это не матан и не алгебра и даже не ТФКП. Есть АЛГОРИТМЫ теории графов. А это несколько другая субстанция.

> Т.к. я не математик, то многое не понятно. Где можно ознакомиться с теорией и формулами в минимальном объеме, чтобы понимать суть алгоритма?

Если сильно хочется, то поищи учебник для технических ВУЗов «Теория графов для инженеров», там изложена наиболее практическая часть, которая может понадобиться инженеру, не связанному с математикой. Но как по мне таких инженеров еще надо поискать, чтобы использовать подобные знания в реале.

> Кто нибудь использует ещё основы теории графов в своих разработках?

Теоретически ТГ может быть полезна при деобфускаации байт-кода 1С8х. Например, для одной частной реализации «обхода бинарного графа в глубину» (это название одного из алгоритмов ТГ). Только один этот стандартный алгоритм ТГ решает проблему деобфускации, процентов на 80. Но для решения остальных 20% нужно уже достаточного много нетривиальных подходов. Всего лишь для практического использования математической теоремы: «Любые эквивалентные преобразования – обратимы». В данном случае, обфускация основана на функциональной эквивалентности. Именно она обратима. А вот синтаксические преобразования при этом не эквивалентны, следовательно – необратимы. И действительно, как восстановить удаленные комментарии и измененные имена? Вот именно, никак :) .

Споршикам что считают что в БП нет графов: http://prntscr.com/mrfic9

Там же
Процедура ЗаписатьОписаниеГрафаДляОтладки(Затраты, МенеджерВременныхТаблиц, Ссылка)
    
    // Записывает представление данных о затратах на языке Dot.
    // Может содержать некоторые прикладные данные (наименования подразделений, номенклатурных групп).
    // Эти данные могут быть полезны для настройки распределения затрат.
    
    Если Не ОбщегоНазначенияКлиентСервер.РежимОтладки() Тогда
        Возврат;
    КонецЕсли;
        
    ЗаписьЖурналаРегистрации(
        ИмяСобытияЖурналаРегистрации("Отладка.ПредставлениеЗатрат"),
        УровеньЖурналаРегистрации.Информация,
        Метаданные.Документы.РегламентнаяОперация,
        Ссылка,
        ОписаниеГрафа(Затраты, МенеджерВременныхТаблиц));
    
КонецПроцедуры

(35) > Споршикам что считают что в БП нет графов: http://prntscr.com/mrfic9

Если вам хочется считать, что это реализовано не ради понтов, а в силу реальной необходимости, то спорить не буду. Раз уж смогли воплотить использование иерархических моделей данных в коде 1С, то разрабы там явно не подрабатывающие студенты, а уровнем несколько повыше, может быть даже с мехмата МГУ или подобных заведений.

Но из того, что что-то можно сделать сложно, не значит, что это нельзя сделать просто. Иерархические данные и иерархические модели отношений известны с времен Царя Гороха. Можно ли для их описания использовать графы? Можно! Но нужно ли? Это вопрос. Похоже, что самый сложный алгоритм ТГ, используемый фирмой 1С, это упомянутый выше «алгоритм обхода графа в глубину». А можно обходить «в ширину» или как-то иначе (в Википедии можно найти подробности). Подобные алгоритмы легко открываются интуитивно, безо всякой ТГ. А реально сложные алгоритмы, например, оптимизация потоков на графах, управление динамическими графами и т.п., фирмой 1С вряд ли используются, иначе это уже будет не системы учета, а системы моделирования реальности, что явно не входит в компетенцию 1С.

Для примера возьмем штатные процедуры 1С выгрузки данных в виде xml (которые можно рассматривать как частный случай графов). Обработки с диска ИТС для обмена xml-данными порождают абсолютно бессмысленный объем данных, который способен повесить любую машину при достаточно больших данных. А если хоть немного оптимизировать этот процесс выгрузки в xml-формат (встроенными процедурами 1С, Карл!), то объем данных можно сократить в десятки и сотни раз.

И так во всем, к чему прикасается 1С8х. Фирма 1С никогда не жалела (особенно в восьмой версии), не жалеет и не будет жалеть ресурсы пользователя. По-видимому, там программируют по принципу, чем больше сжирается ресурсов пользователя, тем лучше. В лучшем случае, это понты, в худшем, злоупотребление собственным положением.

(28) смысл оптимизировать собирание грибов, чем дальше в лес тем больше грибов

(36) язык dot:
https://ru.m.wikipedia.org/wiki/DOT_(язык)

Так они и системы линейных уравнений для учета затрат применяют тоже,чтобы умнее казаться.

в екселе подобные алгоритмы прекрасно решаются иттерациями до достижения определенной точности,и никто не морочится что то анализировать.

(37) Зачем решать задачу интенсивным способом, если можно решить экстенсивным? Фигли думать, если можно трясти?

(39) > язык dot:

Ну и зачем он нужен в 1С? Для рисования блок схем алгоритмов? Или схем работы с документами? Или маршрутов водителей? Понты, они и в Африке понты!

(40) > Так они и системы линейных уравнений для учета затрат применяют тоже, чтобы умнее казаться.  

Теоретически, для распределения затрат при расчете себестоимости это может быть полезным. Однако лучше бы фирма 1С стремилась бы не к усложнению представления и обработки данных, а к их упрощению. Ведь сейчас по-хорошему в ВУЗах пора вводить специальности, с пятилетним сроком обучения, вроде: «1С:Производство», «1С:Бухгалтерия», «1С:Зарплата», настолько усложнились все системы учета от 1С.

(42)
1.ну, допустим, у меня в семерке дот использовался для отрисовки бизнес-процессов.
т.е. есть процесс обработки: из какого состояния в какое объект может переходить (а в какое не может), кто может какие переходы делать, кто может документ в каких состояниях видеть (а кому это не надо и следовательно, он не видит) и т.п.
мне хватало для осознания "невязок" хватало табличной формы. а вот для того, чтоб отдать работу/управление бизнес-процессами обычным сотрудникам, не ИТ-шникам - пришлось делать графическое представление. dot закрыл эту потребность быстро и качественно.

2. "усложнять - просто. упрощать - сложно!"

(41) > Зачем решать задачу интенсивным способом, если можно решить экстенсивным? Фигли думать, если можно трясти?

Это только вопрос цены, которую вы готовы платить. Можно вообще не заморачиваться 1С, типа: «Слюшай, дорогой, я тибе плачу штуку зеленной резанной бумаги и хочу забыть дорогу в налоговую. Ти меня понял?»

(43)  Использовать можно много чего в 1С. Но речь то о чем? Дот это язык описания представления графов, вроде html. Ну, представили вы графы в графическом виде, ну распечатали их, снабдили понятным текстом и рисунками. Ну и что? Какое это имеет отношение к теории графов и их алгоритмам, о которой идет речь в теме топика? Просто вопрос удобства представления данных, не более того.

> "усложнять - просто. упрощать - сложно!"

С этим никто не спорит. Только фирма «1С» явно не намерена (пока!) идти по пути упрощения. Ее больше плющит от процесса усложнения. А разгребать их авгиевы конюшни приходится уже нам – простым программистам :) .

(45) "это имеет отношение к теории графов и их алгоритмам" - да никакого... ответ был на вопрос "зачем нужен dot"

(37) > Если вам хочется считать, что это реализовано не ради понтов, а в силу реальной необходимости, то спорить не буду.

Вот и не спорьте.
Вопрос автора ветки был не в том ради чего это реализовано. Ради понтов или в силу реальной необходимости. Да какая в *опу разница? Оно реализовано. И реализовано именно с использованием простейших алгоритмов ТГ.

А дальше можно сколько угодно обвинять 1С в том, что они выбрали именно алгоритмы ТГ для решения задачи, и что можно было обойтись без них, или наоборот расширить применение ТГ дальше ради оптимизации решения. Сути это не изменит.

И зачем пытаться отрицать очевидное...

(47) > И реализовано именно с использованием простейших алгоритмов ТГ

А вот тут, пожалуйста, поподробнее. «Простейшие алгоритмы ТГ» это какие? Алгоритмы обхода бинарного графа? Если да, то для их придумывания ТГ не нужна. Достаточно здравого смысла. Например, для распутывания обфусцированного байт-кода 1С8 80% всей задачи разрешается с помощью алгоритма одноразового обхода байт-кода «сверху вниз, справа налево». И чем нам здесь поможет ТГ? Ничем! Разве, что предложит перечень подобных алгоритмов (а вам еще нужно понять, что нужен именно этот класс алгоритмов, а не какой-либо другой). Но вот обоснования «справа налево», а не, скажем, «слева направо» не даст. Потому, что это уже специфика последовательности байт-кода.

Да, и «раз уж пошла такая пьянка», то скажите, пожалуйста, а какие структуры данных (например, с точки зрения С++) используются для хранения графов в 1С?

(40) напиши на 1С алгоритм и предоставь его на публику. Посмотрим какой ты у нас мозг.

(45) Если ты покажешь алгоритм, который работает быстрее и проще на партнерском форуме, то его обязательно применят

(50) > Если ты покажешь алгоритм, который работает быстрее и проще на партнерском форуме, то его обязательно применят

Для представления таблиц в xml-формате все достаточно прозрачно. Зачем обрамлять длинючими тегами (для полей таблиц с длинными названиями) каждое поле из, допустим, миллиона записей по 100 – 200 полей в каждой, в таблице, скажем, документа. Достаточно сформировать xml-хидер типов данных таблицы, в котором определить состав и порядок выгружаемых полей таблицы, а также задать разделитель полей и выгружать все поля одной записи в одну строчку. В конце данных текущей таблицы поместить xml-футер.

Для сложных данных, то же представление, но рекурсивное. Главная идея, не повторять имена тегов в одной таблице данных, определяем типы полей и их последовательность только в xml-заголовке текущей таблицы. В крайнем случае, заменять естественные имена полей на числа (символы) из 36-ричной системы счисления (изобретенной фирмой «1С»?).

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

(51) попутная прям пятнично. Эмансипировано в меру, а вот воля не превозмогает

(51)а может сразу в голый текст с разделением запятыми?
xml теги это,конечно,очень не оптимизировано,зато понятно и просто,особенно,если описать типы заранее для пространств имен.

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

(53) > а может сразу в голый текст с разделением запятыми?

Можно и «голый текст», так работала выгрузка данных в «семерке». Можно и dt-формате. Это удобно, пока не нужно делать промежуточную обработку / просмотр / контроль данных.

Однако при «интеллектуальном» переносе данных, когда системы разнородные и стандартная конвертация данных не проходит, удобней иметь текстовый формат, достаточно простой, компактный и вполне однозначный. В этом случае хорошей идеей будет использовать сильные стороны xml-формата и отказаться от его слабых черт.

> xml теги это,конечно,очень не оптимизировано,зато понятно и просто,особенно,если описать типы заранее для пространств имен.

Вот я и предлагаю оптимизировать, причем, достаточно простыми и понятными средствами.

> и вообще,граф это узлы,то есть одна таблица с уникальными номерами,и другая-связи между узламм,там всего два поля по индексам,ну и прочая информация о связи.

Граф, в общем случае, может быть достаточно сложной структурой данных. Причем сложность здесь проявляется в связях, а не узлах. Но в 1С нет слишком сложных структур данных. Все можно свести к схеме данных «один ко многим» и «многие ко одному». Общий граф этими структурами не опишешь, но и места для сложных графов в 1С я не вижу.

А фишка данных 1С в том, что локально это всегда плоские таблицы. А плоские данные удобнее представлять табличными структурами, а не иерархическими. Но связи между таблицами либо табличными частями документа могут быть иерархическими. Поэтому связи, структуру данных и их последовательность выгрузки определяем через xml-формат, а сами плоские данные через локальные таблицы (реально, последовательность полей данных, через разделитель либо микро-теги в одну строку для каждого элемента объекта данных 1С).

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

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

Это все благоглупости! 1С мы критикуем любя. Это хороший продукт на уровне платформы и несколько хуже на уровне конфигураций, поскольку разрабы конф пишут их по принципу «нам с ними не работать». Но даже это не является принципиальной проблемой. При большом желании, можно написать конфигурацию самому либо адаптировать типовую на свой вкус. Сложно? Да, сложно! Но не смертельно! По крайней мере, лучшей альтернативы на горизонте пока что не видно.

Строго говоря, вся эта критика попутная. Появился повод, сказали, что думаем. А поскольку отрицательное цепляет сильнее, чем положительное, то и эмоций по поводу критики больше.

Мне лично от фирмы «1С» ничего не надо. Все, что нужно у них уже есть. Главное, имеется возможность модификации прикладного кода конфигураций, а что еще нужно для полного счастья специалисту по учету на предприятии :) ?

(51) ты рассчитываешь только на свой узенький обмен данными.
Представь, что обмен с помощью xml происходит и с другими системами, которые про твои "хитрые" задумки не знают.
XML - язык, ты можешь применять какие угодно сокращения и т.д., но этому также надо научить других, иначе грош цена таким решениям или это совсем не xml и приплетать сюда 1С как-то странно.

(57) «В огороде бузина, а Киеве – Зеленский!» :) .