Все выпуски  

RusFAQ.ru: Математика


Информационный Канал Subscribe.Ru

РАССЫЛКИ ПОРТАЛА RUSFAQ.RU

/ НАУКА И ОБРАЗОВАНИЕ / Точные науки / Математика

Выпуск № 30
от 02.08.2005, 18:30

Администратор:Tigran K. Kalaidjian
В рассылке:Подписчиков: 55, Экспертов: 14
В номере:Вопросов: 2, Ответов: 2


Вопрос № 24130: Доброго времени суток всем! Подскажите пожалуйста где найти алгоритм поиска всех "циклов" в графе(имеется в виду направленный граф). То есть найти все ситуации когда выходя из одной вершины по исходящей стрелке проходишь определённый путь и...
Вопрос № 24131: Вопрос из синтеза: "смайлик с висилицей" Очень - очень прошу!!! Объясните мне пожалуйста, почему именно то нули в сегменте B не отображается для цифр 5 и 6 и отображаются для всех остальных? пожалуйста.. как для мла...

Вопрос № 24.130
Доброго времени суток всем! Подскажите пожалуйста где найти алгоритм поиска всех "циклов" в графе(имеется в виду направленный граф). То есть найти все ситуации когда выходя из одной вершины по исходящей стрелке проходишь определённый путь и возвращаешься в ту с которой начал:
1-2-3-1
1-2-1
1-1
...
спасибо!!!
Отправлен: 27.07.2005, 23:48
Вопрос задал: DeadRat (статус: Посетитель)
Всего ответов отправлено: 1

Отвечает: mvp
Здравствуйте, DeadRat!
Пусть граф задан в виде матрицы инцедентности А, т. е. строчки и столбцы пронумерованы согласно вершинам графа. А(n, m) = 1, если существует направленное ребро из вершины n в вершину m. Если A(n, n) = 1, то это петля. Если возвести матрицу А в квадрат, то получим вершины, которые связаны маршрутом, длиной два. Если возвести в степень n - длиной n. Если, произвести транзитивное замыкание, то получим матрицу достижимости B = A + A^2 + ... + A^n. B(n, m) <> 0, если существует путь из вершины n в вершину m.
Для вашей задачи суммирование не обязательно, вам нужно лишь возвети матрицы в степени вплоть до n. Обозначим: A(1)=A, A(2) = A^2, ..., A(n) = A^(n). Если А(k)(i, i) = 1, то существует цыкл длиной k, проходящий через вершину i. Чтобы определить, через какие вершины ещё проходит цыкл, смотрим матрицу А(к - 1) на i -ю строку. В ней содержатся вершины, которые достигаюся с i-ой, за k-1 шагов. Нам нужно найти вершину р, такую что А(к-1)(i, p)<>0 и А(1)(p, i) = 1, т. е. из которой есть путь длины 1 в вершину i. Далее рассматриваем матрицу А(k-2) и смотрим на p-ю строку. Нужно найти вершину p1, такую что А(k - 2), (p, p1) <> 0 и А(1)(p1, p) = 1 и т. д., пока не дойдём до А(2). Полученная цепочка в обратном направлении и будет наш цыкл: i- (pk-3)-...-p1-p-i.
Остаётся заметить, что могут быть цыклы разной длины, проходящие через одну вершину, и все они будут найдены. Но ещё могут существовать разные цыклы одинаковой длины, проходящие через одну и туже вершину, тогда поиск назад нужно будет проводит для всех вершин, удовлетворяющих условию (см. выше).
---------
Моя совесть чиста - не бывшая в употреблении
Ответ отправил: mvp (статус: 3-ий класс)
Отправлен: 28.07.2005, 15:47


Вопрос № 24.131

Вопрос из синтеза: "смайлик с висилицей"
Очень - очень прошу!!!
Объясните мне пожалуйста,
почему именно то нули в сегменте B не отображается для цифр 5 и 6
и отображаются для всех остальных?
пожалуйста.. как для младенца.
Объясните...!!!
Не ругайтесь...
"смайлик без висилицы" :-)
Если можно, то скажите, где можно найти подобные примеры таких задач, как синтезировать схемы.

Приложение:

Отправлен: 27.07.2005, 23:51
Вопрос задал: Терсков Алексей Николаевич (статус: Посетитель)
Всего ответов отправлено: 1

Отвечает: Ayl
Здравствуйте, Терсков Алексей Николаевич!

Чего-чего? Какие-такие нули?
Давай сначала.
Вот твой семисегментный элемент:
A
F B
G
E C
D

Расписываем таблицу зависимости сегментов от цифр (таблица 1):
0: A, B, C, D, E, F
1: B, C
2: A, B, D, E, G
3: A, B, C, D, G
4: B, C, F, G
5: A, C, D, F, G
6: A, C, D, E, F, G
7: A, B, C
8: A, B, C, D, E, F, G
9: A, B, C, D, F, G

Т.о., видим, что сегмент B должен гореть при всех цифрах, кроме 5 и 6.
Кодируем цифры с помощью 4-х сигналов x3, x2, x1, x0. Для этого для КАЖДОЙ цифры n мы должны составить такую функцию Fn(X), где X - это множество {x3, x2, x1, x0}, чтобы Fn(n) = 1 и Fn(k) = 0 для k != n.
Такая функция есть конъюнкция переменных x3, x2, x1, x0, причем переменная берется "как есть", если в двоичной записи этой цифры в соответствующем разряде стоит 1, и с отрицанием, если 0.
Получаем 10 функций: F0(X), F1(X), ..., F9(X).

Теперь для каждого элемента e из множества E = {A, B, C, D, E, F, G} 7-ми сегментного индикатора нужно написать функцию G(e, X) такую, чтобы G(e, X) = 1, когда элемент e входит в множество сегментов для цифры n = X' (X' - это значение выражения x3*8+x2*4+x1*2+x0), и G(e, X) = 0 в противном случае (см.Таблицу 1).
Эта функция определяется дизъюнкцией таких Fn(X), для которых в Таблице 1 элемент e входит в множество сегментов для цифры n.

Т.о., для сегмента B функция G(B, X) = F0(X)+F1(X)+F2(X)+F3(X)+F4(X)+F7(X)+F8(X)+F9(X).

А насчет того, почему 0 не отображаются, так это следует из того, как строилась функция G(e, X).

> Очень прошу от вас словестный алгоритм как получились значения функции Fb = 0 для цифр 5 и 6.

Хм. Вообще-то, сначала строится функция G(B, X) и уже в нее подставляются значения X для цифр 5 и 6. Если произведешь все вычисления, то убедишься, что G(e, X) = 0, если X={0,1,0,1} или X={0,1,1,0} и G(e,X)=1 для остальных наборов, кроме двоичных разложений чисел от 10 до 15. Для них тоже 0, т.к. они не учитывались.

Насчет того, где найти. Попробуй в инете по словам: "синтез логических схем", "построение логических схем", "прикладная теория цифровых аппаратов" и т.п.
У меня в институте был курс ПТЦА, там я и научился...
---------
Трудное - то, что можно сделать немедленно. Невозможное - то, для выполнения чего требуется немного больше времени
Ответ отправил: Ayl (статус: Профессор)
Отправлен: 28.07.2005, 12:10
Оценка за ответ: 5
Комментарий оценки:
Да сразу всего не понять!
Буду разбираться!


Отправить вопрос экспертам этой рассылки

Приложение (если необходимо):

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

Обратите внимание!
Вопрос будет отправлен всем экспертам данной рассылки!

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


Форма НЕ работает в почтовых программах The BAT! и MS Outlook (кроме версии 2003+)!
Чтобы отправить вопрос, откройте это письмо в браузере или зайдите на сайт RusFAQ.ru.


© 2001-2005, RusFAQ.ru, Россия, Москва. Все права защищены.
Идея, дизайн, программирование, авторское право: Калашников О.А.

Яндекс


Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора
Подписан адрес:
Код этой рассылки: science.exact.mathematicsfaq
Отписаться
Вспомнить пароль

В избранное