Конференция VBStreets

**kuguar** » 09.06.2005 (Чт) 14:44

Может быть вопрос не в тему, но нигде не могу найти информацию.
Если кто знает - подскажите где можно почитать о методе графов (насколько я понял это что-то вроде двоичного дерева, с количеством ветвей не ограниченным числом 2). Хотелось бы что бы обяъяснение не было слишком заумным.
Если знаете - киньте ссылочку.
С уважением Kuguar :?:

**Опришник** » 11.06.2005 (Сб) 18:10

Граф - это множество вершин V и набор E рёбер. (очень мягкое определение)
На русском это значит что есть вершины и есть связи между вершинами.(необязательно между всеми)
Дерево - это связанный граф не имеющий циклов.
Двоичное дерево это дерево у которого для каждой вершины максимальное количество детей - 2.

О "методе графа" почитать нигде нельзя, такого не существует, есть алгоритмы на графах.

**tyomitch** » 11.06.2005 (Сб) 19:15

Опришник писал(а):Дерево - это связанный граф не имеющий циклов.
Двоичное дерево это дерево у которого для каждой вершины максимальное количество детей - 2.

Не так. У двоичного дерева различаются левый и правый потомок. Т.ч. двоичное дерево - это не частный вид дерева, и даже не граф.

Опришник писал(а):О "методе графа" почитать нигде нельзя, такого не существует, есть алгоритмы на графах.

Я бы не был так строг. Возможно, есть какой-то конкретный алгоритм, называемый "метод графа". Возможно, даже не один.

**Опришник** » 11.06.2005 (Сб) 20:45

tyomitch писал(а):
Опришник писал(а):Дерево - это связанный граф не имеющий циклов.
Двоичное дерево это дерево у которого для каждой вершины максимальное количество детей - 2.

Не так. У двоичного дерева различаются левый и правый потомок. Т.ч. двоичное дерево - это не частный вид дерева, и даже не граф.

Левый и правый потомок - это всего лишь интерпретация, с помощью которой легче понимаются алгоритмы, и которая никакой роли не играет.
А можно вопрос, а почему не граф? (не говоря уже о дереве) Или контр-пример можно? (двоичное дерево ведь вписуется в определение графа)

tyomitch писал(а): Возможно, есть какой-то конкретный алгоритм, называемый "метод графа". Возможно, даже не один.

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

**tyomitch** » 11.06.2005 (Сб) 22:46

Опришник писал(а):
tyomitch писал(а):
Опришник писал(а):Дерево - это связанный граф не имеющий циклов.
Двоичное дерево это дерево у которого для каждой вершины максимальное количество детей - 2.

Не так. У двоичного дерева различаются левый и правый потомок. Т.ч. двоичное дерево - это не частный вид дерева, и даже не граф.

Левый и правый потомок - это всего лишь интерпретация, с помощью которой легче понимаются алгоритмы, и которая никакой роли не играет.

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

Опришник писал(а):А можно вопрос, а почему не граф? (не говоря уже о дереве) Или контр-пример можно? (двоичное дерево ведь вписуется в определение графа)

Блин. Если у графа (или дерева) произвольным образом переставить вершины, получим тот же самый граф (дерево).
Если у B-дерева некоторым образом переставить вершины, получим новое B-дерево.

Пример:

Код: Выделить всё: 1 3 1 / \ / / \ 2 3 1 3 2 / 2

Если трактовать эти картинки как изображения графов (деревьев), то это один и тот же объект. Если как изображения B-деревьев - то три разных объекта.

Поэтому B-дерево - не граф (и не дерево).

Опришник писал(а):
tyomitch писал(а): Возможно, есть какой-то конкретный алгоритм, называемый "метод графа". Возможно, даже не один.

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

**Sasha_karasov** » 12.06.2005 (Вс) 5:35

Вот те книжонка в PDF. А вообще я быстро нашел! Заходишь в google пишешь «Теория графов», и все!
Дерзай! :wink:

**Опришник** » 12.06.2005 (Вс) 13:22

tyomitch писал(а):Обращение порядка всех потомков - да, не играет. Некоторых - совершенно меняет всю картину. Представь себе отсортированное дерево (каждый узел больше своего левого потомка и меньше правого), в нём поиск занимает O(log N) времени именно благодаря тому, что потомки упорядочены.

А теперь переименуем левого потомка в первого, а правого во второго, картина совсем не изменится...(А с утверждением что алгоритм бинарного поиска наглядно демонстрируют только бинарные деревья, я абсолютно согласен)

tyomitch писал(а):Блин. Если у графа (или дерева) произвольным образом переставить вершины, получим тот же самый граф (дерево).
Если у B-дерева некоторым образом переставить вершины, получим новое B-дерево.

Ужасный контр-пример....Вот толко если граф ориентированный, и дерево тоже представить как ориентированный граф(вообще-то так и надо) то произвольным образом переставив вершины, дерево не изменится....

**Опришник** » 12.06.2005 (Вс) 15:23

Sasha_karasov писал(а):Вот те книжонка в PDF. А вообще я быстро нашел! Заходишь в google пишешь «Теория графов», и все!
Дерзай!

Лутше искать "Алгоритмы на графах"...Теория графов - это больше математика.

**tyomitch** » 12.06.2005 (Вс) 20:40

Опришник писал(а):
tyomitch писал(а):Обращение порядка всех потомков - да, не играет. Некоторых - совершенно меняет всю картину. Представь себе отсортированное дерево (каждый узел больше своего левого потомка и меньше правого), в нём поиск занимает O(log N) времени именно благодаря тому, что потомки упорядочены.

А теперь переименуем левого потомка в первого, а правого во второго, картина совсем не изменится...(А с утверждением что алгоритм бинарного поиска наглядно демонстрируют только бинарные деревья, я абсолютно согласен)

См. подчёркнутое

Опришник писал(а):
tyomitch писал(а):Блин. Если у графа (или дерева) произвольным образом переставить вершины, получим тот же самый граф (дерево).
Если у B-дерева некоторым образом переставить вершины, получим новое B-дерево.

Ужасный контр-пример....Вот толко если граф ориентированный, и дерево тоже представить как ориентированный граф(вообще-то так и надо) то произвольным образом переставив вершины, дерево не изменится....

1. Дерево - не ориентированный граф. Графы и ор.графы - не одно и то же, и не надо мешать их в кучу.
2. B-дерево - изменится, именно потому что порядок потомков важен.

Ну как бы тебе понятнее объяснить?
Разница между двумерным вектором и двухэлементным множеством ясна? Тут то же.

**Опришник** » 12.06.2005 (Вс) 23:08

Понял что ты хочешь сказать, но не согласен....
Из курса дискретной математики из определения следует что в дереве порядок потомков не имеет значения....
Но в алгоритмах всё же порядок имеет огромное значение.....

Насчёт

Графы и ор.графы - не одно и то же

это не совсем верно, так как как множество всех ор.графов является подмножеством всех графов(или даже они совпадают)

**tyomitch** » 12.06.2005 (Вс) 23:25

Опришник писал(а):Понял что ты хочешь сказать, но не согласен....
Из курса дискретной математики из определения следует что в дереве порядок потомков не имеет значения....

Правильно.

Опришник писал(а):Но в алгоритмах всё же порядок имеет огромное значение.....

Правильно.
Из этих двух фактов и следует вывод: B-деревья - не деревья.

Опришник писал(а):Насчёт
Графы и ор.графы - не одно и то же

это не совсем верно, так как как множество всех ор.графов является подмножеством всех графов(или даже они совпадают)

Не так. Это разные объекты. Так же, как пресловутые вектора и множества.

**Опришник** » 12.06.2005 (Вс) 23:31

tyomitch писал(а):
Опришник писал(а):Понял что ты хочешь сказать, но не согласен....
Из курса дискретной математики из определения следует что в дереве порядок потомков не имеет значения....

Правильно.
Опришник писал(а):Но в алгоритмах всё же порядок имеет огромное значение.....

Правильно.
Из этих двух фактов и следует вывод: B-деревья - не деревья.

Не понял что ты хочешь сказать...
И следует скорее противоположное....

tyomitch писал(а):Не так. Это разные объекты. Так же, как пресловутые вектора и множества.

А ты попробуй построить граф который не будет представим с помощью ор.графа, и вообще также попробуй и дерево построить и Б-дерево....

**tyomitch** » 12.06.2005 (Вс) 23:52

Опришник писал(а):А ты попробуй построить граф который не будет представим с помощью ор.графа, и вообще также попробуй и дерево построить и Б-дерево....

А ты попробуй построить множество, которое не будет представимо с помощью вектора.
(Блин, вот здесь чат бы здорово оказался кстати :-)

)

**Опришник** » 13.06.2005 (Пн) 0:49

tyomitch писал(а):
Опришник писал(а):А ты попробуй построить граф который не будет представим с помощью ор.графа, и вообще также попробуй и дерево построить и Б-дерево....

А ты попробуй построить множество, которое не будет представимо с помощью вектора.

{1,2,3,4,5} оно же {5,4,3,2,1} (тебе аж 120 векторов понадобится чтоб представить...)

tyomitch писал(а):(Блин, вот здесь чат бы здорово оказался кстати )

Нада сделать тему "ЧАТ", и там все будут всякое писать...
Со временем админов замучает совесть и они сделают чат... :-)

**Sasha_karasov** » 13.06.2005 (Пн) 2:43

Опришник писал(а):
Sasha_karasov писал(а):Вот те книжонка в PDF. А вообще я быстро нашел! Заходишь в google пишешь «Теория графов», и все!
Дерзай!

Лутше искать "Алгоритмы на графах"...Теория графов - это больше математика.

Графы – это и есть математики
Программирование – это тоже типа математики

**tyomitch** » 13.06.2005 (Пн) 14:18

Опришник писал(а):
tyomitch писал(а):
Опришник писал(а):А ты попробуй построить граф который не будет представим с помощью ор.графа, и вообще также попробуй и дерево построить и Б-дерево....

А ты попробуй построить множество, которое не будет представимо с помощью вектора.

{1,2,3,4,5} оно же {5,4,3,2,1} (тебе аж 120 векторов понадобится чтоб представить...)

Прекрасно. Значит, вот такой граф не представим с помощью ор.графа:
1-2-3-4-5
Тебе аж 16 ор.графов понадобится чтоб представить...

**Опришник** » 13.06.2005 (Пн) 21:04

Sasha_karasov писал(а):Графы – это и есть математики
Программирование – это тоже типа математики

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

**Опришник** » 13.06.2005 (Пн) 21:07

tyomitch писал(а):
Опришник писал(а):
tyomitch писал(а):
Опришник писал(а):А ты попробуй построить граф который не будет представим с помощью ор.графа, и вообще также попробуй и дерево построить и Б-дерево....

А ты попробуй построить множество, которое не будет представимо с помощью вектора.

{1,2,3,4,5} оно же {5,4,3,2,1} (тебе аж 120 векторов понадобится чтоб представить...)

Прекрасно. Значит, вот такой граф не представим с помощью ор.графа:
1-2-3-4-5
Тебе аж 16 ор.графов понадобится чтоб представить...

Меняем - на <-> и всё...

**tyomitch** » 13.06.2005 (Пн) 21:45

Опришник писал(а):
tyomitch писал(а):Прекрасно. Значит, вот такой граф не представим с помощью ор.графа:
1-2-3-4-5
Тебе аж 16 ор.графов понадобится чтоб представить...

Меняем - на <-> и всё...

Прекрасно. А как представить с помощью графа вот такой ор.граф?
1->2<->3<-4<-5 :?:

напомню: чуть раньше ты писал(а):множество всех ор.графов является подмножеством всех графов(или даже они совпадают)

**Опришник** » 13.06.2005 (Пн) 22:01

tyomitch писал(а):Прекрасно. А как представить с помощью графа вот такой ор.граф?
1->2<->3<-4<-5

С помощью не ориентированного графа никак, а что?

tyomitch писал(а):
напомню: чуть раньше ты писал(а):множество всех ор.графов является подмножеством всех графов(или даже они совпадают)

А что не так разве? Просто я настаиваю на том, что {графы} = {ор.графы} U {не ор.графы}

**tyomitch** » 13.06.2005 (Пн) 23:50

Опришник писал(а):
tyomitch писал(а):Прекрасно. А как представить с помощью графа вот такой ор.граф?
1->2<->3<-4<-5

С помощью не ориентированного графа никак, а что?

Значит, ор.графов "больше", чем неор.графов.
(Раз каждому неор.графу соотв. ор.граф, и не каждому ор.графу соотв. неор.граф)

Опришник писал(а):
tyomitch писал(а):
напомню: чуть раньше ты писал(а):множество всех ор.графов является подмножеством всех графов(или даже они совпадают)

А что не так разве? Просто я настаиваю на том, что {графы} = {ор.графы} U {не ор.графы}

Как может быть большее частью меньшего?

**GSerg** » 14.06.2005 (Вт) 5:22

tyomitch писал(а):Как может быть большее частью меньшего?

Нет, я не разбираюсь в теории графов...
Просто на эту фразу хочу ответить...

Как-то раз я сохранял реестр одной Win98 в текстовый файл. Сохранил весь реестр. Получилось около 3 метров.
Сразу поле этого я выделил одну ветку этого реестра (DYN_DATA) и сохранил только её. Получилось почти 8 метров.

**Опришник** » 14.06.2005 (Вт) 10:37

tyomitch писал(а):Значит, ор.графов "больше", чем неор.графов.
(Раз каждому неор.графу соотв. ор.граф, и не каждому ор.графу соотв. неор.граф)

напомню: чуть раньше я писал(а):множество всех ор.графов является подмножеством всех графов(или даже они совпадают)

Совпадают они, если {неор.графы} є {ор.графы}

tyomitch писал(а):...Как может быть большее частью меньшего?

Не корректо поставленный вопрос!!!
Что большее, а что меньшее?

**Опришник** » 14.06.2005 (Вт) 10:52

GSerg писал(а):
tyomitch писал(а):Как может быть большее частью меньшего?

Нет, я не разбираюсь в теории графов...
Просто на эту фразу хочу ответить...

Как-то раз я сохранял реестр одной Win98 в текстовый файл. Сохранил весь реестр. Получилось около 3 метров.
Сразу поле этого я выделил одну ветку этого реестра (DYN_DATA) и сохранил только её. Получилось почти 8 метров.

не, это не парадокс...
Просто с момента сохранения всего реестра и до момента сохранения DYN_DATA, он незначительно вырос... (Win98 так умеет)

**uhm** » 14.06.2005 (Вт) 10:59

tyomitch, ты иногда такие вещи говоришь, которые противоречат моим фундаментальным представлениям об устройстве Вселенной. Самое страшное, что иногда ты бываешь прав... :lol:

И все-таки:

1) Дерево - граф с одной вершиной (корневой вершиной), в которую нет входящих ребер, а в каждую другую вершину входит только одно ребро. (www.glossary.ru)

2) Двоичным деревом поиска (ДДП) называют дерево, все вершины которого упорядочены, каждая вершина имеет не более двух потомков (назовём их левым и правым), и все вершины, кроме корня, имеют родителя. (http://www.rsdn.ru/article/alg/binstree.xml)

А не следует ли из этого, что двоичное дерево поиска является частным случаем графа (как я всю жизнь и считал)?

ЗЫ Твой контрпример не катит, если графы рассматривать как упорядоченные.

**uhm** » 14.06.2005 (Вт) 11:00

ЗЗЫ Ориентированные и упорядоченные (на всякий случай) - это разные вещи!

**tyomitch** » 14.06.2005 (Вт) 11:27

uhm, "обычные" графы никто не рассматривает как упорядоченные - в отличие от B-деревьев. Упорядоченные и неупорядоченные графы (на всякий случай) - это разные реши!

Твоё определение из glossary.ru относится к ориентированному дереву. Определение, данное в своём первом посте Опришником - к неориентированному дереву. Ориентированные и неориентированные деревья (на всякий случай) - это разные вещи!

Упорядоченный граф не может быть частным случем неупорядоченного так же, как вектор не может быть частным случаем множества.

2Опришник: неориентированное дерево, представленное по твоей "методике" в виде ор.графа, ориентированным деревом уже не будет. Согласен?
Если да, то это аргумент в пользу несмешения ор.графов и неор.графов.

Ещё попрошу определить понятие "просто графа" - элемента множества "всех графов".
Если "{графы} = {ор.графы} U {не ор.графы}", то упорядоченные графы туда как бы не попадают, да?