Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 16
Простите, если совсем не в тему напишу.
Почему это подается аксиомой? Что является признаком близости?
Мне из этого видится вывод, что Евклидовая близость никак не ответит на вопросы «как изменится пропускная способность между районами», «несет ли новое ребро экономическую выгоду»
Понятно, что даже одна полоса сблизит районы
Почему это подается аксиомой? Что является признаком близости?
Получается также, что с точки зрения расстояний добавление к двухполосной дороге по одной полосе с каждой стороны эквивалентно добавлению трех полос с одной. Евклидова близость в обоих случаях увеличится в два раза. Занятно.
Мне из этого видится вывод, что Евклидовая близость никак не ответит на вопросы «как изменится пропускная способность между районами», «несет ли новое ребро экономическую выгоду»
Самое смешное, что, скорее всего, дополнительные полосы в одну сторону скорее всего ухудшат ситуацию с транспортной доступностью — станет больше машин в обратном направлении, пропускная способность обратной (единственной) полосы начнет падать из за резкого падения средней скорости движения вызванного увеличением числа автомобилей, и, следовательно, уменьшением дистанции между автомобилями.
Но тут в модели это не было учтено, так как термин «дорога между районами города» был использован лишь для иллюстрации задачи на графе.
IMHO
PS. Вот тут есть симулятор пропускной способности полосы: traffic-simulation.de/ring.html
Но тут в модели это не было учтено, так как термин «дорога между районами города» был использован лишь для иллюстрации задачи на графе.
IMHO
PS. Вот тут есть симулятор пропускной способности полосы: traffic-simulation.de/ring.html
Почему это подается аксиомой? Что является признаком близости?
Хм. Вся статья — это попытка рассказать, как можно определить близость через обычное евклидово расстояние.
Итак, есть направленный граф с двумя вершинами (узлами)
Серьезно, вы применяете аппарат теории графов для графа из двух вершин?
Насколько будут ближе районы, если построить еще одну полосу в одном направлении?
[trolling] А что, добавление новой дороги меняет положение районов в пространстве? Напоминает мне старый подкол «Что тяжелее: килограмм ваты или килограмм гвоздей?»[/trolling]
А если серьезно
Вопрос — насколько изменится расстояние между узлами, если проводимость в одном из направлений увеличить вдвое?
Связь «расстояния» и «пропускной» способности у вас нигде не задается, поэтому все, что написано в статье — это просто набор алгебраических преобразований без какого-либо смысла.
З.Ы. Если словосочетания network flows, wardrop equilibria ничего вам не говорят, то скорее всего в тематике пропускных способностей на графах вы новичок.
Серьезно, вы применяете аппарат теории графов для графа из двух вершин?
) Извиняюсь, конечно. А на какое количество вершин рассчитан этот аппарат?
… все, что написано в статье — это просто набор алгебраических преобразований без какого-либо смысла.
… скорее всего в тематике пропускных способностей на графах вы новичок.
) Люблю такое, бодрит. Надеюсь в скором времени увидеть правильную статью на хабре про wardrop equilibria. Мы новички всегда открыты для новых знаний.
В последнее время играю в OpenTTD. По моему опыту, если пропускная способность A-B недостаточна для нужд потока, а пропускная способность B-A больше A-B, то в конечном счёте по пути B-A за единицу времени будет проходить тот же поток, что и через A-B. Если, конечно, в городе B нет завода по производству транспорта и работает закон сохранения транспорта, а также нет аварий и поломок.
Для учёта аварий резистивное расстояние тоже не подходит. Честно говоря, не могу представить бытовую интерпретацию резистивного расстояния для задачи о пропускной способности дорог.
Для учёта аварий резистивное расстояние тоже не подходит. Честно говоря, не могу представить бытовую интерпретацию резистивного расстояния для задачи о пропускной способности дорог.
Для такого простого графа потоку просто некуда деваться, — сколько вошло, столько и вышло. Баланс потоков сохраняется. Подробнее о балансе потоков и потенциалах узлов для обеспечения баланса есть в предыдущих статьях (про Салтана). Терминология правда местами немного уточнилась.
Вообще поскольку в статье приведен пример орграфа на основе дорог, то народ стал думать в основном в сторону транспорта и потоков. Это вполне нормально, и уверен, что там можно обнаружить правильные интерпретации, если чуть копнуть. Обнаружится какое-нибудь «время средней достижимости».
Но направленных графов полно и в других областях.
На примере тех же лайков. Вы мне лайк, я вам лайк — мы подружились (появилось расстояние). В статье рассчитано, насколько сильнее станет наша дружба, если я вам ещё один лайк дам. Несложная интерпретация.
Вообще поскольку в статье приведен пример орграфа на основе дорог, то народ стал думать в основном в сторону транспорта и потоков. Это вполне нормально, и уверен, что там можно обнаружить правильные интерпретации, если чуть копнуть. Обнаружится какое-нибудь «время средней достижимости».
Но направленных графов полно и в других областях.
На примере тех же лайков. Вы мне лайк, я вам лайк — мы подружились (появилось расстояние). В статье рассчитано, насколько сильнее станет наша дружба, если я вам ещё один лайк дам. Несложная интерпретация.
Подскажите, пожалуйста.
Возьмем симплекс в евклидовом пространстве и выпишем матрицу расстояний между его вершинами, свойства которой очевидны: она симметрична и ее элементы, положительные или — на главной диагонали — нулевые, удовлетворяют неравенству треугольника. Это необходимые свойства. Спрашивается, чего недостает, чтобы матрица с такими свойствами была матрицей расстояний между вершинами некоторого симплекса в евклидовом пространстве?
Возьмем, например, тетраэдр и уменьшим его высоту до нуля. Тогда указанные свойства будут иметь место, но это не симплекс.
Возьмем симплекс в евклидовом пространстве и выпишем матрицу расстояний между его вершинами, свойства которой очевидны: она симметрична и ее элементы, положительные или — на главной диагонали — нулевые, удовлетворяют неравенству треугольника. Это необходимые свойства. Спрашивается, чего недостает, чтобы матрица с такими свойствами была матрицей расстояний между вершинами некоторого симплекса в евклидовом пространстве?
Возьмем, например, тетраэдр и уменьшим его высоту до нуля. Тогда указанные свойства будут иметь место, но это не симплекс.
Если я правильно понял вопрос, то у правильного симплекса детерминант его полного грамиана должен быть отрицательным.
Грамиан — матрица скалярных произведений между элементами, здесь — вершинами симплекса. Если нормы элементов равны нулю (вершины являются точками), то значения матрицы — это квадраты расстояний, деленные на (-2).
Для того, чтобы грамиан был полным, надо окаймить его единицами, в углу оставить ноль. Это значения скалярных произведений вершин симплекса и нуль-вектора пространства.
Более подробно есть здесь, формула (1.6).
Грамиан — матрица скалярных произведений между элементами, здесь — вершинами симплекса. Если нормы элементов равны нулю (вершины являются точками), то значения матрицы — это квадраты расстояний, деленные на (-2).
Для того, чтобы грамиан был полным, надо окаймить его единицами, в углу оставить ноль. Это значения скалярных произведений вершин симплекса и нуль-вектора пространства.
Более подробно есть здесь, формула (1.6).
Нет, симплекс любой, не обязательно правильный. Т.е. имеем произвольную матрицу с указанными свойствами, выписываем по ней полный грамиан, его определитель оказывается отрицательным — и что, достаточно этого, чтобы наша матрица была матрицей расстояний между вершинами некоторого симплекса, тем более правильного?
Другими словами, мне хочется знать, каковы необходимые и достаточные условия того, чтобы (произвольно взятая) матрица была матрицей расстояний для некоторого симплекса.
Другими словами, мне хочется знать, каковы необходимые и достаточные условия того, чтобы (произвольно взятая) матрица была матрицей расстояний для некоторого симплекса.
А как это доказывается? И почему об этом ни слова в Википедии?
«Я под правильным симплексом тут понимаю такой, квадрат объема которого является положительным числом.» Что же, объем «неправильного» симплекса может быть неположительным?
«Я под правильным симплексом тут понимаю такой, квадрат объема которого является положительным числом.» Что же, объем «неправильного» симплекса может быть неположительным?
Если вы хотите глубоко копнуть эту тему, то вам надо поднимать ссылки по теме Distance geometry. Народ выяснением условий для правильных дистанций давно интересовался. Одна из ключевых работ для своего времени — «Remarks to Maurice Frechet's Article» (Schoenberg ,1935).
Отрицательность детерминанта полного грамиана — это наиболее простое условие, из которого при желании можно вывести кучу разных других лемм. Скорее всего доказательство есть в какой-нибудь монографии про матрицу евклидовых расстояний.
Отрицательность детерминанта полного грамиана — это наиболее простое условие, из которого при желании можно вывести кучу разных других лемм. Скорее всего доказательство есть в какой-нибудь монографии про матрицу евклидовых расстояний.
Да, спасибо. По-видимому, то что надо. Я потом, возможно, еще кое-что спрошу, с Вашего разрешения конечно.
Оказывается, мой вопрос о необходимых и достаточных условиях существования симплекса в евклидовом пространстве по матрице расстояний между его вершинами подробно рассмотрен в книге М. Берже «Геометрия», 1984 (теорема 9.7.3.4 и замечание 9.7.3.5). Действительно, определитель Кэли — Менгера должен быть ненулевым и иметь нужный знак в зависимости от числа вершин симплекса. Причем ничего больше проверять не надо, ни симметричность матрицы, ни неотрицательность ее элементов, ни неравенство треугольника. Я-то ожидал несколько по-другому. Доказательство, может быть, и несложно, но лишь для тех, кто в теме, а не просто так погулять вышел. ))
Кстати, да. Я в Бержа давно уже не заглядывал, но на начальном этапе тоже пытался разобраться, о чем он там толкует.
В целом все верно у него, только имхо переусложнено. Это следствие того, что он (как и многие другие) не использует явным образом понятие скалярного произведения элементов (привыкли только векторы перемножать). Тут как будто бы слепое пятно у людей. Не матрица Кэли-Менгера является основой, а грамиан. Не расстояния — а скалярные произведения.
Ну а второе ключевое понятие — нуль-вектор. С ним становится понятно, откуда появляется в грамиане окаймление из 1. Ну и в целом аффинная метрическая геометрия становится на твердую основу.
В аффинной геометрии плоскость определяется не 3-мя точками, а 4-мя. В этом ключ к пониманию.
В целом все верно у него, только имхо переусложнено. Это следствие того, что он (как и многие другие) не использует явным образом понятие скалярного произведения элементов (привыкли только векторы перемножать). Тут как будто бы слепое пятно у людей. Не матрица Кэли-Менгера является основой, а грамиан. Не расстояния — а скалярные произведения.
Ну а второе ключевое понятие — нуль-вектор. С ним становится понятно, откуда появляется в грамиане окаймление из 1. Ну и в целом аффинная метрическая геометрия становится на твердую основу.
В аффинной геометрии плоскость определяется не 3-мя точками, а 4-мя. В этом ключ к пониманию.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
О близости вершин