miniatura| O grafo orientado (ou digrafo) da dereita é unha orientación do grafo non orientado da esquerda. 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