Как отличить решётку от графа

[katevector]

Путь, т.к. нам ещё давали такое предложение:
Решетку часто представляют ориентированным графом, вершинам которого соответствуют элементы решетки, и если a<=b, то в графе существует путь из a в b.

[Xaositect]

А, ну тогда все хорошо. Решения, которые Вы писали, верные.

[katevector]

А если бы это был не путь, а просто стрелка, то тогда в первом примере, например, для пары (1,3) не было бы вообще общей верхней и нижней грани?

А в Вашем примере, если я ничего не путаю, для
(A,B): p - нижняя, x - верхняя
(B,C): s - нижняя, y - верхняя
(A,C): A - нижняя, C - верхняя

[Xaositect]

Верно.

[katevector]

Xaositect, спасибо Вам большое за разъяснения и за то что время на меня потратили!
Теперь мне понятно:)
Спасибо большое ещё раз!

[katevector]

В процессе решения задач столкнулась ещё с одной проблемой относительно решёток, оказалось, этот момент я до конца для себя не прояснила.
Например, на картинке есть задание: определить, решётка или нет.

И для пары (3,4) я столкнулась с тем, что не могу определиться, какая вершина является нижней границей - 1 или 2, т.к. они обе подходят под определение нижней границы.
Помогите, пожалуйста, разобраться с этой проблемой.
Заранее спасибо!

[bot]

katevector в сообщении #647643 писал(а):

т.к. они обе подходят под определение нижней границы

А Вам разве всякая нижняя граница нужна? А просто убрать лишние стрелочки не пробовали?

[katevector]

Дошло:) действительно, убрать лишние стрелочки - помогло.
т.к. нужна наибольшая нижняя граница, то нижней границей в данном случае будет 1, верно?

В этом примере пытаюсь аналогично разобраться, но тоже застряла (определить нижнюю границу (A,B)). Почему x, а не y?
Также пробую "закрыть" лишние стрелки, но тут пока не вижу (от A до x - 2 шага, от A до y - 1 шаг; и от B до y - 2 шага, от B до x 1 шаг).

Xaositect в сообщении #632792 писал(а):

Верно.
-- Пт окт 19, 2012 14:04:01 --
Какие будут верхняя и нижняя грань у $A$ и $B$, $B$ и $C$, $A$ и $C$?

$$ \xymatrix{ & & p \ar[dl] \ar[d] \ar[dr] & &\\ & q \ar[d] & r \ar[dd] & s \ar[dr] \ar[ddl] & \\ & A \ar[dr] \ar[dddr] \ar[dl] & & & t \ar[d] \\ u \ar[dr] & & v \ar[dl] \ar[dr] & & B \ar[dl] \\ & C \ar [dr] & & x \ar[dl] & \\ & & y & & } $$

[bot]

katevector в сообщении #647664 писал(а):

убрать лишние стрелочки - помогло.

А может быть и здесь поможет, а?

[katevector]

Стараюсь, даже стёрла


Я сейчас для себя совсем примитивно попробовала так сформулировать:
вершина y: рёбра в неё только направлены
вершина x: ребра направлены как в неё, так и из неё
Поэтому x - наименьшая верхняя граница.

[bot]

Вот у Вас остался прямой рейс $A\to y$, в то время как есть транзитный $A\to v\to x\to y$. А куда у Вас пропали вершины $r, u, c$?

[katevector]

А я их что-то уже и со счетов списала.

[bot]

Как-то Вы странно выбрасываете. Был прямой рейс $s\to v$, а теперь и транзитного нет, зато

bot в сообщении #648070 писал(а):

Вот у Вас остался прямой рейс $A\to y$

[katevector]

Я, может, что-то не так понимаю, но рейс s->v не проходит через A вершину, зачем тогда его рассматривать?
Я поняла так: например, если мы рассматриваем пару (A,B), тоо и рейсы начинаем рассматривать с A и B соответственно.
Все возможные рейсы из A:

A->u
A->v
A->u->С
A->v->C
A->u->С->y
A->v->С->y
A->v->x
A->v->x->y
A->y

Все возможные рейсы из B:
B->x
B->x->y

т.к. пути из B в C, u, v нет, то вершина C, u, v не может быть границей => рассматривать рейсы
A->u->С
A->v->C
A->u->С->y
A->v->С->y

смысла нет.

Остались рейсы

A->v->x
A->v->x->y
A->y
B->x
B->x->y

По определению : для a, b из X элемент c=a+b из X называется наименьшей верхней границей, если выполняется:
1). a<=c, b<=c; 2) для любого d из X, если a<=d, b<=d => c<=d.

А дальше застряла...

[bot]

bot в сообщении #648148 писал(а):

Был прямой рейс $s\to v$, а теперь и транзитного нет

Удаление этого ребра неправомерно. Удалить можно ребро, которое может быть получено по транзитивности из остальных, таковым здесь является ребро $A\to y$.