Орграфы

В теории ориентированных графов сделано так много, что на эту тему можно написать целую книгу. В настоящей главе мы уделяем особое внимание тем свойствам орграфов, которые отличают их от графов. Поэтому мы начнем с введения трех различных типов соединимости: сильной, односторонней и слабой. Сформулировав принцип ориентированной двойственности, мы перейдем к изучению матриц, связанных с орграфами, и затем приведем аналог матричной теоремы о деревьях в графах. Глава заканчивается кратким описанием турниров и их свойств.