Grafo distância-regular

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
O grafo de Shrikhande, um grafo distância-regular.
Famílias de grafos definidos por seus automorfismos
distância-transitivo \rightarrow distância-regular \leftarrow fortemente regular
\downarrow
simétrico (arco-transitivo) \leftarrow t-transitivo, t ≥ 2 .
\downarrow
(se conectado)
transitivo nos vértices e nas arestas \rightarrow aresta-transitivo e regular \rightarrow aresta-transitivo
\downarrow \downarrow
vértice-transitivo \rightarrow regular
\uparrow
grafo de Cayley anti-simétrico assimétrico


No campo da matemática da teoria dos grafos, um grafo distância-regular é um grafo regular tal que para quaisquer dois vértices v e w a uma distância i o número de vértices adjacentes a w e à distância j a partir de v é o mesmo. Todo grafo distância-transitivo é distância regular. Com efeito, grafos distância-regular foram introduzidos como uma generalização combinatória de grafos distância-transitivos, tendo as propriedades de regularidade numérica do último, sem ter necessariamente um grande grupo de automorfismo.

Alternativamente, um grafo distância-regular é um grafo para o qual existem inteiros bi,ci,i=0,...,d tais que para quaisquer dois vértices x, y em G e distância i=d(x,y), há exatamente ci vizinhos de y em Gi-1(x) e bi vizinhos de y em Gi+1(x), onde Gi(x) é o conjunto de vértices y de G com d(x,y)=i (Brouwer et al. 1989, p. 434).[1] O array de inteiros caracterizando um grafo distância regular é conhecido como o seu array de interseção.

Um grafo distância-regular com diâmetro 2 é fortemente regular, e reciprocamente (a menos que o grafo seja desconexo).

Números Intersecção[editar | editar código-fonte]

É usual utilizar a seguinte notação para um grafo distância-regular G. O número de vértices é n. O número de vizinhos de w (Isto é, os vértices adjacentes a w) cuja distância de v é i, i + 1, e i − 1 é denotada por ai, bi, e ci, respectivamente; estes são os números de intersecção de G. Obviamente, a0 = 0, c0 = 0, e b0 é igual a k, o grau de qualquer vértice. Se G tem um diâmetro finito, então d denota o diâmetro enós temos bd = 0. Também temos que ai+bi+ci= k

Os numeros ai, bi, e ci são frequentemente mostrados em um array de três linhas.

\left\{\begin{matrix} - & c_1 & \cdots & c_{d-1} & c_d \\ a_0 & a_1 & \cdots & a_{d-1} & a_d \\ b_0 & b_1 & \cdots & b_{d-1} & - \end{matrix}\right\},

chamado o array de intersecção de G. Eles podem ser formados também por uma matriz tridiagonal

B:= \begin{pmatrix} a_0 & b_0 & 0 & \cdots & 0 & 0 \\
c_1 & a_1 & b_1 & \cdots & 0 & 0 \\
0 & c_2 & a_2 & \cdots & 0 & 0 \\
\vdots & \vdots & \vdots &  & \vdots & \vdots \\
0 & 0 & 0 & \cdots & a_{d-1} & b_{d-1} \\
0 & 0 & 0 & \cdots & c_d & a_d \end{pmatrix} ,

chamada de matriz de intersecção.

Matrizes de adjacência distância[editar | editar código-fonte]

Suponha que G é um grafo distância-regular conexo. Para cada distância i = 1, ..., d, podemos formar um grafo Gi no qual os vértices são adjacentes se sua distância em G é igual a i. Façamos Ai ser a matriz de adjacência de Gi. Por exemplo, A1 é a matriz de adjacência A de G. Além disso, seja A0 = I, a matriz identidade. Isto nos dá d + 1 matrizes A0, A1, ..., Ad, chamadas as matrizes de distância de G. A soma é a matriz J em que cada entrada é 1. Há uma fórmula de produto importante:

A A_i = a_i A_i + b_i A_{i+1} + c_i A_{i-1} .

A partir desta fórmula resulta que cada Ai é uma função polinomial de A, de grau i, e que A satisfaz um polinômio de grau d + 1. Além disso, A tem exatamente d + 1 autovalores distintos, dos quais o maior é k, o grau.

As matrizes de distância abrangem um subespaço vetorial do espaço vetorial de todas n × n matrizes reais. É um fato notável que o produto Ai Aj de quaisquer duas matrizes de distância é uma combinação linear das matrizes de distância:

A_i A_j = \sum_{k=0}^d p_{ij}^k A_k .

Isto significa que as matrizes de distância geram um esquema de associação. A teoria dos esquemas de associação é fundamental para o estudo dos gráficos de distância regular. Por exemplo, o fato de que Ai é uma função polinomial de A é um fato sobre os esquemas de associação.

Exemplos[editar | editar código-fonte]

Referências

  1. BROUWER, Andries E.;COHEN, A.M.; NEUMAIER, A.. Distance Regular Graphs. Berlin, New York: Springer-Verlag, 1989. p. 434. ISBN 3-540-50619-5, ISBN 0-387-50619-5.