Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Descrete Math] Vertex Basis - что это?

Автор: KatrinIceLand 24.1.2008, 16:27

Всем привет! У меня тут термин (Vertex basis) с которым я никак не могу разобраться.  Сижу, решаю задачки на графы по математике и тут, прямо в упражнениях встречается новый термин Vertex basis и задачка: Даны direct graphs и значит у каждой их них надо найти этот самый vertex basis. В учебнике об этом ни слова. Ну я конечно сразу гугл это и ничего! не предлагается   , такое в моей практике впервые. Там конечно высветилось что-то про basis vertex function, но это не то.  Мне не функция нужна, а определение какие vertices являются basis и почему, в общем как мне в этих графах найти эти точки?? PLS HELP.

Автор: KatrinIceLand 25.1.2008, 15:31

Да уж, похоже что никто даже и слышал ничего об этом. Господа математики, мы с вами на пороге нового открытия   А если серьезно, попалось мне в одной книжечке по алгорифмам определение, но оно еще больше меня запутало. Посмотрите, может кто-нибудm поймет и расшифрует это определение для народа, дабы просвятить    ну и мне помочь, все же курсовую сдавать надо. Вот этот шифр: Vertex basis in direct graph is a set of vertices such that there is a path to every vertex in the graph not in the set from some vertex in this set and there is no path from any vertex in the set to another vertex in the set.    WOW Всем приятных выходных!

Автор: kBepTu 25.1.2008, 18:57

Цитата Vertex basis in direct graph is a set of vertices such that there is a path to every vertex in the graph not in the set from some vertex in this set and there is no path from any vertex in the set to another vertex in the set Здесь даеться определение базиса вершин графа. Не знаю что такое "direct graph". Определение получилось мудренным    Начинаеться так: Базис вершин direct графа - это множество таких вершин, что ..      ЗЫ: когда то что то делали с вычеркиванием вершин в графе, но сейчас не помню. Мб это?

Автор: maxim1000 25.1.2008, 19:18

directed graph, насколько я понимаю - ориентированный граф базис, как я понял из определения, - набор точек, из которых можно добраться до любой вершины графа + между точками базиса нет переходов смысл тот же, что и в других областях: базис - минимальный набор, из которого каким-либо образом можно получить всё остальное, минимальный в смысле "ничего нельзя выкинуть"

Автор: KatrinIceLand 25.1.2008, 20:00

Цитата(maxim1000 @  25.1.2008,  19:18 ) directed graph, насколько я понимаю - ориентированный граф Exactly!  Цитата(kBepTu @  25.1.2008,  18:57 ) Базис вершин direct графа Попыталась поискать по этому переводу, все равно ничего пояснительного не нашла. Цитата(maxim1000 @  25.1.2008,  19:18 ) базис - минимальный набор, из которого каким-либо образом можно получить всё остальное, минимальный в смысле "ничего нельзя выкинуть"  Похоже не правду по определению, но никак не понятен смыл    Вот например у меня есть 3 ориентированных графа. (Я напишу в adjancy matrix что бы не чертить): 1)    a b c d  a 1 0 0 0 b 1 0 1 0 c  0 0 0 1 d  1 1 1 0 2)    a b c d a 0 1 0 0 b 1 1 1 0 c  1 0 0 0 d 0 0 0 1 3)    a b c d  a 0 1 0 0 b 1 0 1 1 c  1 0 0 1 d 1 0 0 0 Так с чего мне начать? Как определить какие вершины являются базис вершинами ?...

Автор: maxim1000 25.1.2008, 22:10

Цитата(KatrinIceLand @  25.1.2008,  20:00 ) Похоже не правду по определению, но никак не понятен смыл смысл такой: минимальный набор точек, из которого можно прийти в любую вершину единственное, что меня смущает: Цитата(kBepTu @  25.1.2008,  18:57 ) and there is no path from any vertex in the set to another vertex in the set т.е. если у нас есть d->c  и с->d, базиса выбрать не получается так что то, как я понимаю, отличается от определения в этой части дальше - то, как я понимаю: 1. {d} или {c}, или {b} 2. {a,d} или {b,d}, или {c,d} 3. {a} или {b}, или {c}, или {d}

Автор: KatrinIceLand 26.1.2008, 02:25

Цитата(maxim1000 @  25.1.2008,  22:10 ) единственное, что меня смущает: Цитата(kBepTu @  25.1.2008,  18:57 ) and there is no path from any vertex in the set to another vertex in the set Вот именно это предложение меня и сбивало с толка, но сейчас посидев и подумав над этим определение у меня похоже что то получилось    Vertex basis in direct graph is a set of vertices such that there is a path to every vertex in the graph not in the set from some vertex in this set -  Базис вершин в ориентированном графе это набор вершин (точек) в таком порядке что от каждой вершины этого набора есть путь к каждой вершине данного графа не находящегося в этом наборе.  and there is no path from any vertex in the set to another vertex in the set -  и при условии что в этом наборе вершин нет ПУТИ между вершинами из этого набора!    По-моему теперь звучит логично. Но разгадывать эти самые вершины у меня сейчас нет настроения, попробую на днях и выложу здесь мои варианты ответов, а вы пожалуйста оспорьте если будете не согласны. Самое главное это то что мы разобрались с этим определением    maxim1000 спасибо за помощь! Без тебя я бы не додумалась!

Автор: KatrinIceLand 29.1.2008, 12:38

Цитата(maxim1000 @  25.1.2008,  22:10 ) дальше - то, как я понимаю: 1. {d} или {c}, или {b} 2. {a,d} или {b,d}, или {c,d} 3. {a} или {b}, или {c}, или {d}  Насколько я понимаю, в 1. может быть только {d}, это едиственная вершина которая соединяется со всеми другими вершинами в графе. А в вариантах 2. и 3. я не уверена. Мне кажется в этих графах вообще нет этих базиз вершин. 0, 0.

Автор: maxim1000 29.1.2008, 13:42

Цитата(KatrinIceLand @  29.1.2008,  12:38 ) Насколько я понимаю, в 1. может быть только {d}, это едиственная вершина которая соединяется со всеми другими вершинами в графе. не совсем d - единственная вершина, которая имеет рёбра ко всем остальным но в определении говорится "path", а не "edge", т.е. необязательно, чтобы до любой вершины можно было попасть за один шаг - достаточно наличия последовательности например, {c} может быть базисом, т.к. из c можно попасть куда-угодно (через d) за 2 шага (ну до d за один)

Автор: KatrinIceLand 29.1.2008, 13:52

Цитата(maxim1000 @  29.1.2008,  13:42 ) в определении говорится "path", а не "edge",  Точно! ок, в 1. {d} или {c} или {b}  - согласна. А во втором случае? Там же вершина {d} вообще ни с одной вершиной не соединяется. Тогда нет базиз вершин? То же самое и в третьем случае с вершиной е.

Автор: maxim1000 29.1.2008, 16:02

Цитата(KatrinIceLand @  29.1.2008,  13:52 ) А во втором случае? Там же вершина {d} вообще ни с одной вершиной не соединяется. Тогда нет базиз вершин? базис не обязан быть одной вершиной тут можно поступить по аналогии с линейной алгеброй: ввести понятие "база" база - набор вершин, из которых можно добраться до любой вершины графа тогда базис можно назвать минимальной базой (т.е. такая база, из которой нельзя выкинуть ни одной вершины, оставляя её базой) тогда очевидно, что базис всегда есть: достаточно взять какую-то базу (например, просто все вершины графа) и выкидывать из неё точки, пока можно во втором случае у нас есть, например, {a,d} из них можно добраться в c,b а до a и d добираться не нужно - они и так в базисе

Автор: KatrinIceLand 29.1.2008, 16:51

maxim1000,  спасибо за объяснения! Поняла и согласна с пунктами 1 и 2.  Цитата(maxim1000 @  25.1.2008,  22:10 ) 1. {d} или {c}, или {b} 2. {a,d} или {b,d}, или {c,d} 3. {a} или {b}, или {c}, или {d}  Но тогда по аналогии со вторым пунктом базис вершин у нас может быть только с вершиной {e} включительно. Я имею ввиду {a,e}, {b,e}, {c,e}, и {d,e} соответственно... Или нет? Извиняюсь за столько вопросов, просто хочу убедится что поняла эту тему.

Автор: maxim1000 29.1.2008, 18:55

Цитата(KatrinIceLand @  29.1.2008,  16:51 ) Но тогда по аналогии со вторым пунктом базис вершин у нас может быть только с вершиной {e} включительно. Я имею ввиду {a,e}, {b,e}, {c,e}, и {d,e} соответственно... Или нет? e? там, вроде, нету e...

Автор: KatrinIceLand 29.1.2008, 19:11

Цитата(KatrinIceLand @  25.1.2008,  20:00 ) 3)    a b c d  a 0 1 0 0 b 1 0 1 1 c  1 0 0 1 d 1 0 0 0 Цитата(maxim1000 @  29.1.2008,  18:55 ) e? там, вроде, нету e...  SORRy! Конечно там нету {е}, я ее не вписала   . Правильный вариант: 3)    a b c d e a 0 1 0 0 0 b 1 0 1 1 0 c  1 0 0 1 0 d 1 0 0 0 0 e 0 0 0 0 0 в общем отдельно стоящая точка, без any edges.

Автор: maxim1000 29.1.2008, 19:18

ну тогда да, она должна присутствовать в каждом базисе Добавлено через 2 минуты и 42 секунды да и вообще, можно вывести, например, такое свойство: если граф несвязный, то можно сначала понаходить базисы для каждой связной облсати, а потом комбинировать их всеми способами, при которых в наборе присутствует один базис для каждой области связности в последнем примере это области {e} и {a,b,c,d} вот и получается, что для первой области всё однозначно и просто, а для второй возможны 4 варианта, значит всего 4х1 вариантов

Автор: KatrinIceLand 29.1.2008, 19:25

Цитата(maxim1000 @  29.1.2008,  19:18 ) ну тогда да, она должна присутствовать в каждом базисе Ну похоже что разобрались    Спасибо!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)