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

[katevector]

Помогите, пожалуйста, разобраться, как отличить решётку от графа.
Я понимаю, что решётка - это частный случай графа, и что у решётки существует наименьшая верхняя граница и наибольшая нижняя.
Но как это определить на графе - решётка это или нет, я не понимаю.
Подскажите, пожалуйста, как разобраться.
Заранее благодарю!

[VAL]

Во-первых, если рассматривать решетку с этих позиций, то как частный случай орграфа, а не просто графа.
Во-вторых, точную верхнюю и точную нижнюю грань должна иметь любая пара элементов (а не только сама решетка).
Вот на основании этого "во-вторых" и определяйте.

[katevector]

Извините, всё равно не совсем понимаю.
Например, есть граф. Он решётка.

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

[Xaositect]

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

Например, я понимаю (если считать слева-направо), что вторая и третья вершина (т.е. пара элементов) имеют верхнюю и нижнюю грань (первую и четвёртую вершины). А как же тогда пара вершин - первая и четвёртая вершины?

Верхней и нижней гранью второй и третьей вершины будут вторая и третья вершина. Там в определении неравенства нестрогие.

[katevector]

Поняла, т.е. для первой и четвёртой - верхней и нижней гранью и будет первая и четвёртая вершины, верно?
Тогда получается, что любой ориентированный граф - решётка (раз у любой пары вершин в ориентированном графе можно найти верхнюю и нижнюю грань)?

[VAL]

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

Извините, всё равно не совсем понимаю.
Например, есть граф. Он решётка.

По существу Вам уже ответили.
Я лишь добавлю, что лучше ориентировать граф по вертикали, а не слева направо. Тогда понятия верхней и нижней граней станут нагляднее.

[Xaositect]

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

Поняла, т.е. для первой и четвёртой - верхней и нижней гранью и будет первая и четвёртая вершины, верно?

Верно.

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

Тогда получается, что любой ориентированный граф - решётка (раз у любой пары вершин в ориентированном графе можно найти верхнюю и нижнюю грань)?

Неверно. Найдите верхнюю грань у $a$ и $b$ в таком графе:

$$ \xymatrix{ a\ar@{->}[dr] & & b\ar@{->}[dl]\\ & z &\\ } $$

[katevector]

Если я правильно поняла, то верхней гранью для a и b будет z (т.к. общая вершина, к которой направлены стрелки).
А нижней нет, т.к. нет общей вершины, ОТ которой вели бы стрелки к a и b.
Похоже на правду?

[Xaositect]

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

[katevector]

В первой задаче я теперь рассуждаю так:
для пары
(1,2): 1 - нижняя, 2 - верхняя
(1,3): 1 - нижняя, 3 - верхняя
(1,4): 1 - нижняя, 4 - верхняя

(2,3): 2 - нижняя, 3 - верхняя
(2,4): 2 - нижняя, 4 - верхняя

(3,4): 3 - нижняя, 4 - верхняя

[Xaositect]

Верно.

-- Пт окт 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 & & } $$

[katevector]

Спасибо большое за ответы, вроде бы стало понятно!
Можете ещё, если не трудно, один пример проверить, чтобы я уже точно была уверена, что верно поняла:



(1,2): 1 - нижняя, 2 - верхняя
(1,3): 1 - нижняя, 3 - верхняя
(1,4): 1 - нижняя, 4 - верхняя
(1,5): 1 - нижняя, 5 - верхняя

(2,3): 2 - нижняя, 3 - верхняя
(2,4): 2 - нижняя, 4 - верхняя
(2,5): 2 - нижняя, 5 - верхняя

(3,4): 3 - нижняя, 4 - верхняя
(3,5): 3 - нижняя, 5 - верхняя

(4,5): 3 - нижняя, а верхней нет => это не решётка.

[Xaositect]

Верно.

-- Пт окт 19, 2012 14:11:22 --

Так, стоп.
Вы, пожалуйста, приведите те определения верхней/нижней грани, которые Вам давали, точно.
А то вот в последнем случае у Вас все стрелочки прорисованы, $1\to 2$, $2\to 3$, $1\to 3$.
А в первом примере между $1$ и $3$ стрелочки нет, они будут связаны через вторую вершину или нет?

[katevector]

Определения:

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

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

[Xaositect]

Так, а $\leqslant$ - это когда в графе есть стрелка из $a$ и $b$, или когда есть путь из $a$ и $b$?