 |
|
Модераторы: Poseidon |
 
|
|
[Descrete Math] Vertex Basis - что это? Кто-нибудь сталкивался с этим термином? 
| KatrinIceLand |
|
|||
 Бывалый  Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
Всем привет!
У меня тут термин (Vertex basis) с которым я никак не могу разобраться. Сижу, решаю задачки на графы по математике и тут, прямо в упражнениях встречается новый термин Vertex basis и задачка: Даны direct graphs и значит у каждой их них надо найти этот самый vertex basis. В учебнике об этом ни слова. Ну я конечно сразу гугл это и ничего! не предлагается  , такое в моей практике впервые. Там конечно высветилось что-то про basis vertex function, но это не то. Мне не функция нужна, а определение какие vertices являются basis и почему, в общем как мне в этих графах найти эти точки?? PLS HELP. --------------------
[... кто изобрел математику? А зачем?... |
|||
|
||||
Загрузка ...
| KatrinIceLand |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
Да уж, похоже что никто даже и слышал ничего об этом. Господа математики, мы с вами на пороге нового открытия
 А если серьезно, попалось мне в одной книжечке по алгорифмам определение, но оно еще больше меня запутало. Посмотрите, может кто-нибуд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 |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 68 Регистрация: 6.12.2007 Репутация: 2 Всего: 2 |
Здесь даеться определение базиса вершин графа. Не знаю что такое "direct graph". Определение получилось мудренным  Начинаеться так: Базис вершин direct графа - это множество таких вершин, что ..  ЗЫ: когда то что то делали с вычеркиванием вершин в графе, но сейчас не помню. Мб это? Это сообщение отредактировал(а) kBepTu - 25.1.2008, 19:01 |
|||
|
||||
| maxim1000 |
|
|||
 Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
directed graph, насколько я понимаю - ориентированный граф
базис, как я понял из определения, - набор точек, из которых можно добраться до любой вершины графа + между точками базиса нет переходов смысл тот же, что и в других областях: базис - минимальный набор, из которого каким-либо образом можно получить всё остальное, минимальный в смысле "ничего нельзя выкинуть" -------------------- qqq |
|||
|
||||
| KatrinIceLand |
|
||||||
|
Бывалый Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
Exactly!
Попыталась поискать по этому переводу, все равно ничего пояснительного не нашла.
Похоже не правду по определению, но никак не понятен смыл Вот например у меня есть 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 Так с чего мне начать? Как определить какие вершины являются базис вершинами ?... --------------------
[... кто изобрел математику? А зачем?... |
||||||
|
|||||||
Дата 25.1.2008, 20:00 (
| maxim1000 |
|
||||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
смысл такой: минимальный набор точек, из которого можно прийти в любую вершину единственное, что меня смущает:
т.е. если у нас есть d->c и с->d, базиса выбрать не получается так что то, как я понимаю, отличается от определения в этой части дальше - то, как я понимаю: 1. {d} или {c}, или {b} 2. {a,d} или {b,d}, или {c,d} 3. {a} или {b}, или {c}, или {d} -------------------- qqq |
||||
|
|||||
| KatrinIceLand |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
Вот именно это предложение меня и сбивало с толка, но сейчас посидев и подумав над этим определение у меня похоже что то получилось 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 |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
Насколько я понимаю, в 1. может быть только {d}, это едиственная вершина которая соединяется со всеми другими вершинами в графе. А в вариантах 2. и 3. я не уверена. Мне кажется в этих графах вообще нет этих базиз вершин. 0, 0. --------------------
[... кто изобрел математику? А зачем?... |
|||
|
||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
не совсем d - единственная вершина, которая имеет рёбра ко всем остальным но в определении говорится "path", а не "edge", т.е. необязательно, чтобы до любой вершины можно было попасть за один шаг - достаточно наличия последовательности например, {c} может быть базисом, т.к. из c можно попасть куда-угодно (через d) за 2 шага (ну до d за один) -------------------- qqq |
|||
|
||||
| KatrinIceLand |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
Точно! ок, в 1. {d} или {c} или {b} - согласна. А во втором случае? Там же вершина {d} вообще ни с одной вершиной не соединяется. Тогда нет базиз вершин? То же самое и в третьем случае с вершиной е. --------------------
[... кто изобрел математику? А зачем?... |
|||
|
||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
базис не обязан быть одной вершиной тут можно поступить по аналогии с линейной алгеброй: ввести понятие "база" база - набор вершин, из которых можно добраться до любой вершины графа тогда базис можно назвать минимальной базой (т.е. такая база, из которой нельзя выкинуть ни одной вершины, оставляя её базой) тогда очевидно, что базис всегда есть: достаточно взять какую-то базу (например, просто все вершины графа) и выкидывать из неё точки, пока можно во втором случае у нас есть, например, {a,d} из них можно добраться в c,b а до a и d добираться не нужно - они и так в базисе -------------------- qqq |
|||
|
||||
| KatrinIceLand |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
maxim1000,
спасибо за объяснения! Поняла и согласна с пунктами 1 и 2.
Но тогда по аналогии со вторым пунктом базис вершин у нас может быть только с вершиной {e} включительно. Я имею ввиду {a,e}, {b,e}, {c,e}, и {d,e} соответственно... Или нет? Извиняюсь за столько вопросов, просто хочу убедится что поняла эту тему. --------------------
[... кто изобрел математику? А зачем?... |
|||
|
||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
e? там, вроде, нету e... -------------------- qqq |
|||
|
||||
| KatrinIceLand |
|
||||
|
Бывалый Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
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 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
ну тогда да, она должна присутствовать в каждом базисе
Добавлено через 2 минуты и 42 секунды да и вообще, можно вывести, например, такое свойство: если граф несвязный, то можно сначала понаходить базисы для каждой связной облсати, а потом комбинировать их всеми способами, при которых в наборе присутствует один базис для каждой области связности в последнем примере это области {e} и {a,b,c,d} вот и получается, что для первой области всё однозначно и просто, а для второй возможны 4 варианта, значит всего 4х1 вариантов -------------------- qqq |
|||
|
||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.0551 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |