Orientación (teoría de grafos)

Na teoría de grafos, unha orientación dun grafo non orientado é unha asignación dunha dirección a cada aresta, convertendo o grafo inicial nun grafo orientado.

 Grafos orientados simples 
Nun  grafo orientado simple ningún dos seus pares de vértices está unido por dúas arestas mutuamente simétricas. É dicir, como máximo só un de  ou  poden ser frechas da gráfica.

Un torneo é unha orientación dun grafo completo. 

Unha poliárbore é unha orientación dunha árbore non orientada. A conxectura de Sumner afirma que todo torneo con  vértices contén cada poliárbore con  vértices.

O número de grafos orientados non isomorfos con  vértices (para  ) é

 1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, … .

 Orientacións restrinxidas 
Unha orientación forte é unha orientación que dá como resultado un grafo fortemente conexo. As orientacións totalmente cíclicas estreitamente relacionadas son orientacións nas que cada aresta pertence polo menos a un ciclo simple.

Unha orientación dun grafo non orientado  é totalmente cíclica se e só se é unha orientación forte de cada compoñente conexa de  . 

O teorema de Robbins afirma que un grafo ten unha orientación forte se e só se está conectada por dúas arestas. 

Os grafos desconectados poden ter orientacións totalmente cíclicas, mais só se non teñen pontes..
 Notas 


 Véxase tamén 


 Outros artigos 
 Relación conexa
 Ligazóns externas 

Categoría:Teoría de grafos