ROUGH DRAFT authorea.com/89690
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • Grafos String

    Grafos de interseção de curvas foram introduzidos por Sinden em (Sinden 1966) num estudo sobre circuitos RC e, mais tarde, estudados em (Ehrlich 1976). O termo ”grafos string” foi introduzido por Graham em (Graham 1976) propondo o problema de caracterização desta classe de grafos. Este trabalho faz uma breve introdução a classe de grafos string.

    Introdução

    Seja \(S\) um conjunto finito de curvas no plano. Dizemos que duas curvas \(a,b\in S\) se intersectam se eles têm ao menos um ponto em comum e denotaremos por \(a\cap b\neq\emptyset\). O grafo \(G=(V,E)\) tal que \(V=S\) e \(ab\in E\) se, e somente se, as curvas \(a\) e \(b\) se intersectam é o grafo de interseção de \(S\). E um grafo \(G\) é string se existe um conjunto de curvas no plano no qual \(G\) é o grafo de interseção de \(S\) e dizemos que \(S\) é uma representação de curvas de \(G\). Como cada curva corresponde a um vértice, utilizaremos os termos vértice e curva indistintamente.

    Formalizando as definições, uma curva é uma função \(\gamma:I\rightarrow\mathbb{R}^{2}\) homeomorfa a sua imagem, onde \(I=[0,1]\). E duas curvas \(\gamma\) e \(\delta\) se intersectam se existem \(s,t\in I\) tais que \(\gamma(s)=\delta(t)\).

    TODO incluir exemplos

    \label{lemma:prop}

    Todo grafo string possui uma representação de string satisfazendo:

    1. 1.

      duas curvas se intersectam um número finito de vezes,

    2. 2.

      por cada ponto passam no máximo duas curvas, e

    3. 3.

      se \(deg(u)\leq 2\), então a curva de \(u\) possui somente um ponto de interseção com cada um de seus vizinhos.

    Proof.
    1. 1.

      TODO trivial?!

    2. 2.

      Sempre podemos alterar as curvas localmente em torno do ponto de interseção entre três ou mais curvas de modo que haja somente interseções entre duas curvas.

    3. 3.

      Temos dois casos. Primeiramente, se \(deg(u)=1\), então basta reduzirmos a curva \(u\) de forma a ter somente uma única interseção com o seu único vizinho. Se \(deg(u)=2\) e \(\gamma\) é a curva representando \(u\), então existem \(s<t\in I\) tais que \(\gamma(s)\) é uma interseção com um dos vizinhos de \(u\), \(\gamma(t)\) é uma interseção com o outro vizinho de \(u\) e \(\gamma\) não possui nenhuma interseção no intervalo \((s,t)\). Então, podemos substituir a curva \(\gamma\) por \(\gamma^{\prime}=\gamma|_{[s-\epsilon_{0},t+\epsilon_{1}]}\) para algum \(\epsilon_{0},\epsilon_{1}>0\).

    Mostraremos agora que a classe de grafos string é um subconjunto próprio do conjunto de grafos através do seguinte resultado.

    Dado um grafo \(G\), seja \(G^{\prime}\) o grafo resultante da subdivisão de cada aresta de \(G\). Temos que \(G^{\prime}\) é grafo string se, e somente se, \(G\) é planar.

    Proof.

    Se \(G\) é planar, então \(G^{\prime}\) também é planar. Logo, \(G^{\prime}\) é grafo string (ver \ref{prop:planar}). Por outro lado, assuma que \(G^{\prime}\) é grafo string. Seja \(R\) uma representação de curvas de \(G\). Temos que os vértices de \(G\) em \(G^{\prime}\) estão representadas por curvas que só possuem interseção com as curvas que representam os vértices da subdivisão. Estes, por sua vez, têm exatamente duas interseções: uma para cada vértice de \(G\) adjacente. Assim, sem perda, podemos assumir que as interseções dessas curvas ocorrem exatamente nos extremos. Se contrairmos as curvas que representam os vértices de \(G\) a um ponto, teremos uma representação plana de \(G\). Portanto, \(G\) é planar. ∎

    O grafo resultante da subdivisão das arestas do \(K_{5}\) não é grafo string.

    TODO incluir figuras

    Subclasses de Grafos String

    Apresentaremos nesta seção algumas classes de grafos e como elas estão relacionadas a classe de grafos string. Começaremos apresentando o resultado já utilizado na seção anterior.

    \label{prop:planar}

    Todo grafo planar é grafo string.

    Proof.

    Dado um grafo planar, podemos construir a sua representação de curvas a partir de sua representação plana da seguinte forma: para cada vértice, faça uma curva contornando o vértice e pouco mais da metade das arestas incidentes ao vértice (ver TODO figura)). Dessa forma, todas as interseções entre curvas ocorrem no meio de cada aresta: as curvas relativas ao vértices extremos da aresta se cruzam duas vezes. TODO incluir figura

    Antes de prosseguirmos com outras classes de grafos, enunciaremos o seguinte resultado que segue do \ref{lemma:prop} e realizando uma construção semelhante a prova da \ref{prop:planar}. A partir dele, será fácil concluir que grafos cordais também são grafos string e, consequentemente, várias subclasses de cordais, como grafos de intervalo, estrelado, split, etc., também são.

    Grafos string são exatamente os grafos de interseção de caminhos (ou subárvores) de um grafo planar.

    Grafos cordais são grafos string.

    Proof.

    Grafos cordais são grafos de interseção de subárvores de um árvore. E como toda árvore é um grafo planar, segue do teorema que todo grafo cordal é grafo string. ∎

    Mostraremos a seguir que todo grafo de co-comparabilidade também são grafos string. No entanto, não é verdade que todo grafo de comparabilidade é string. Considere o grafo da figura (TODO figura do k5 subdividido). Ele é de comparabilidade, pois é bipartido, mas, não é string.

    Um grafo é de função se é um grafo de interseção de gráficos de funções contínuas \(f:I\rightarrow\mathbb{R}\).

    Claramente, grafos de função são grafos string, pois gráficos de uma função são curvas do tipo \(\gamma:I\rightarrow\mathbb{R}^{2}\), \(\gamma(t)=(t,f(t))\). Note também que grafos de função é uma generalização da classe de grafos de permutação, dado que obtemos esta última assumindo que as funções são lineares.

    Se \(S=\{f_{1},\dots,f_{n}\}\) é uma família de funções contínuas de \(I\) em \(\mathbb{R}\) e \(G=\Omega(S)\), então a sua representação por curvas é chamada de diagrama de funções. E, se todas as funções são lineares, chamaremos de diagrama de permutação.

    Um grafo \(G\) é de função se, e somente se, \(\overline{G}\) é de comparabilidade.

    Proof.

    Seja \(G\) um grafo de função e sejam \(\gamma_{v}:I\rightarrow\mathbb{R}^{2}\), \(\gamma_{v}(t)=(t,f_{v}(t))\), para \(v\in V(G)\), as curvas que representam cada vértice de \(G\). Como os vértices \(u\) e \(v\) são adjacentes em \(\overline{G}\) se, e somente se, \(\gamma_{u}\) e \(\gamma_{v}\) não se cruzam, podemos definir a seguinte orientação \(F\) em \(\overline{G}\): \(uv\in F\Leftrightarrow f_{u}(t)<f_{v}(t)\quad\forall t\in I\). É claro que se \(uv\in F\) e \(vw\in F\), então \(f_{u}(t)<f_{v}(t)<f_{w}(t)\quad\forall t\in I\) e, portanto, \(uw\in F\). Logo, \(F\) é transitiva e \(\overline{G}\) é grafo de comparabilidade.

    Por outro lado, seja \(\overline{G}\) um grafo de comparabilidade sobre um poset \(P=(X,<)\), onde \(X=V(G)\), e seja \(\mathscr{L}=\{L_{0},\dots,L_{k}\}\) um realizador de \(P\) (ver apêndice \ref{sec:poset} para definições e propriedades de posets). Sejam \(D_{i}\), \(1\leq i\leq k\), o diagrama de permutação das ordens totais \(L_{i-1}\) e \(L_{i}\). Assim, a concatenação dos diagramas \(D_{1},\dots,D_{k}\) resulta num diagrama de funções \(D\) tal que cada função é linear por partes. Mostraremos que \(D\) é um diagrama de funções de \(G\). Para isso, temos que mostrar que \(uv\in G\Leftrightarrow f_{u}\text{ e }f_{v}\text{ se cruzam}\). Se \(uv\in G\), então \(u\) e \(v\) não são comparáveis em \(P\). Logo, existem \(L_{i}\) e \(L_{j}\) tais que \(u<_{i}v\) e \(v<_{j}u\), o que implica \(f_{u}\) e \(f_{v}\) se cruzarem em algum momento entre \(L_{i}\) e \(L_{j}\). Reciprocamente, se \(uv\notin G\), então \(u\) e \(v\) são comparáveis em \(P\). Logo, ou \(u<_{i}v\) para todo \(L_{i}\in\mathscr{L}\) ou \(v<_{i}u\) para todo \(L_{i}\in\mathscr{L}\). Em qualquer um dos casos, as curvas \(f_{u}\) e \(f_{v}\) são disjuntas.

    TODO incluir diagramas