grafos:proparvnorm_i

Demonstração i):

Seja $P$ um caminho qualquer de $x$ a $y$ em $G$, vamos mostrar que $P$ passa por $\lceil x\rceil \cap \lceil y\rceil$.

Se $x$ é comparável a $y$, acabamos, pois $y \in \lceil x\rceil$ ou $x \in \lceil y\rceil$, caso contrário:

Seja $t_1,\ldots,t_n$ uma sequência minimal de vértices em $P\cap T$ tais que $t_1=x$ e $t_n = y$ satisfazendo $t_i$ comparável a $t_{i+1}$ $\forall i$ na ordem de $T$ (esta sequência existe, pois todo segmento $t_iPt_{i+1}$ está contido em $T$ ou é um $T$-caminho e $T$ é normal em $G$).

(Note ainda que cada $t_i$, que não seja $x$ ou $y$, está na “bifurcação” dos “ramos” visto que para ir de um “ramo” para outro por vértices satisfazendo $t_i$ comparável a $t_{i+1}\forall i$, se faz necessário passar por estas “bifurcações”).

Note que não podemos ter $t_{i-1}<t_i>t_{i+1}$, pois teríamos a existência de $rTt_{i-1}Tt_i$ e de $rTt_{i+1}Tt_i$, mas como $rTt_i$ há de ser um caminho único, ou $\exists rTt_{i-1}Tt_{i+1}$ ou $\exists rTt_{i+1}Tt_{i-1}$, de qualquer maneira, $t_{i-1}$ é comparável com $t_{i+1}$, o que faz $t_i$ ser desnecessário, contrariando a proposição da sequencia ser minimal.

Tem-se, portanto:

$$x=t_1>\ldots>t_k<\ldots<t_n=y$$

Para algum $k \in \{1,\ldots,n\}$. $t_k \in \lceil x\rceil \cap \lceil y\rceil \cap V(P)$ como queríamos demonstrar.

  • grafos/proparvnorm_i.txt
  • Última modificação: 2022/04/06 17:27
  • por 127.0.0.1