Gerichtete Nachbarschaften und Grad-Konzepte

In gerichteten Graphen wird das klassische Nachbarschafts- und Gradkonzept anhand der Kantenorientierung strikt in ein- und ausgehende Komponenten aufgespalten.

• Ausgehende Nachbarschaft ($N^{+}$): Die Menge aller Nachfolger, die über eine vom Knoten $v$ wegführende Kante direkt erreicht werden:$$N^{+}(v)\triangleq \{u\in V(G)\mid (v,u)\in E(G)\}$$
• Eingehende Nachbarschaft ($N^{-}$): Die Menge aller Vorgänger, deren gerichtete Kante direkt im Knoten $v$ mündet:$$N^{-}(v)\triangleq \{u\in V(G)\mid (u,v)\in E(G)\}$$
• Grad-Definitionen: Die Kardinalitäten dieser Mengen definieren den Ausgangsgrad $d^{+}(v)=|N^{+}(v)|$ und den Eingangsgrad $d^{-}(v)=|N^{-}(v)|$.

Links

• DS_vollständiger_foliensatz.pdf