W teorii grafów wyróżniamy dwa podstawowe typy grafów — skierowane i nieskierowane. Ponieważ będziemy wykorzystywać oba te typy, więc zdefiniujemy je poniżej.

Podkreślmy, że w teorii grafów nieskierowanych, którą będziemy się posługiwać, nie można połączyć dwóch wierzchołków więcej niż jedną krawędzią. Grafy nieskierowane z wieloma krawędziami opisuje teoria multigrafów. Natomiast w przypadku grafów skierowanych możemy mieć krawędź od stanu a do stanu b oraz od stanu b do stanu a. Z takimi grafami mamy do czynienia np. przy grafach przejścia łańcuchów Markowa, gdzie możemy z pewnym prawdopodobieństwem przejść ze stanu a do stanu b jak i ze stanu b do stanu do stanu a.

Grafy są często wykorzystywane w teorii transportu, więc wiele pojęć w tej teorii nosi nazwy związane z przemieszczeniem się.

Zauważmy, że ponieważ długość ścieżki t≥0, to w szczególności przy t=0 mamy ścieżkę u1, która ma długość 0. Natomiast nie ma innych ścieżek łączących wierzchołek z samym sobą.

Ponieważ ścieżka jest w jednoznaczny sposób wyznaczona przez występujące w niej krawędzie, więc będziemy w skrócie pisać u1, u2,…,ut+1 zamiast u1, a1, u2,…,ut+1.

Z istnieniem ścieżek łączy się też pojęcie osiągalności.

Oczywiście w grafie nieskierowanym, jeśli v jest osiągalne z u, to u jest osiągalne z v, natomiast w grafie skierowanym taka implikacja w ogólnym przypadku nie musi być prawdziwa. W związku z tym w przypadku grafu nieskierowanego możemy mówić o tym, że dwa wierzchołki komunikują się (lub są ze sobą połączone). Zauważmy też, że

Korzystając z pojęcia długości ścieżki możemy teraz zdefiniować odległość dwóch wierzchołków.

Zauważmy, że tak zdefiniowana odległość w grafie skierowanym nie spełnia wszystkich aksjomatów metryki, ponieważ nie musi być symetryczna. Co więcej, jeśli wierzchołek v jest osiągalny z u, to nie oznacza, że u jest osiągalne z v, zatem odległość d⁢u,v może być zdefiniowana, natomiast odległość d⁢v,u — nie musi. Dla przykładu — w systemie komunikacyjnym miasta, jeśli wprowadzamy ulice jednokierunkowe, to musimy zadbać, żeby wszystkie istotne miejsca miały zdefiniowaną odległość.

Zauważmy dalej, że d⁢u,u=0, ponieważ założyliśmy, że u jest ścieżką. Odległość w grafie nieskierowanym spełnia też nierówność trójkąta.

Teraz spróbujemy opisać ekosystem siedliska za pomocą łańcuchów pokarmowych. Siedliskiem nazwiemy obszar ograniczony i w pewien sposób wydzielony, w którym żyją różne gatunki roślin i zwierząt. Tworzą one łańcuch pokarmowy, który odzwierciedlamy za pomocą grafu skierowanego, w którym wierzchołkami są gatunki, natomiast krawędź skierowana prowadzi od gatunku u do v, jeśli u jest drapieżnikiem dla v. Z danym łańcuchem pokarmowym związujemy też graf konkurencji, który z kolei stanowi graf nieskierowany z tymi samymi wierzchołkami, a krawędzie łączą dwa wierzchołki, jeśli odpowiadające im gatunki konkurują o to samo pożywienie.

Łańcuchy pokarmowe możemy badać na różne sposoby. Przedstawimy tutaj koncepcję statusu troficznego (pokarmowego) zaadaptowaną z socjologicznej teorii organizacji. W ekologii socjologiczne pojęcie statusu osobnika w schemacie organizacji odpowiada poziomowi (stopniowi) troficznemu gatunku. Chcemy w taki sposób odzwierciedlić złożoność i różnorodność łańcuchów pokarmowych. Jeśli na każdym poziomie troficznym w danym łańcuchu pokarmowym jest wiele gatunków, to powiemy, że taki łańcuch jest różnorodny. Wspominaliśmy już, że w ekologii uważa się, iż łańcuchy bardziej złożone są też bardziej stabilne. Chcemy więc móc określić co to znaczy, że dany łańcuch jest bardziej złożony.

Pojęcie poziomu troficznego dość łatwo zdefiniować w przypadku prostych łańcuchów pokarmowych opisywanych za pomocą specyficznych grafów zwanych drzewami. W strukturze drzewa występuje jeden wyróżniony wierzchołek zwany korzeniem, do którego nie prowadzą żadne krawędzie wchodzące, zatem nie ma też żadnych ścieżek prowadzących od jakiegokolwiek innego wierzchołka do korzenia. Struktura drzewa jest rekurencyjna — jeśli usuniemy korzeń wraz z prowadzącymi zeń krawędziami, to powstaną oddzielne grafy o analogicznej strukturze, których korzeniami są wierzchołki bezpośrednio osiągalne z pierwotnego korzenia, por. rys. 14.2.

W takiej rekurencyjnej strukturze, jeśli procedurę usuwania korzeni przeprowadzimy dostatecznie wiele razy, to na końcu dostaniemy pojedyncze wierzchołki (czasem mówi się o liściach drzewa). Liczba usunięć przeprowadzająca dany wierzchołek na korzeń nowego grafu jest ściśle związana z poziomem troficznym gatunku reprezentowanego przez ten wierzchołek w drzewie. Jeśli maksymalna liczba możliwych usunięć w danym drzewie wynosi m, a liczba usunięć, która tworzy z danego wierzchołka korzeń — k, to poziom troficzny gatunku odpowiadającego temu wierzchołkowi równa się m-k.

W ogólnym przypadku dla złożonego łańcucha pokarmowego znacznie trudniej zdefiniować analog tego pojęcia. Zdefiniujemy miarę statusu troficznego w celu odróżnienia od ,,zwykłego” poziomu troficznego, łatwego do wyznaczenia w prostych strukturach. Zanim przejdziemy do zaproponowania takiej definicji wprowadzimy odpowiednie założenia. Zakładamy, że graf opisujący łańcuch pokarmowy jest acykliczny, czyli wśród ścieżek tego grafu nie da się wyróżnić cyklu. W szczególności nie ma dwóch gatunków u i v, takich że jednocześnie u jest drapieżnikiem dla v i v jest drapieżnikiem dla u. Dla takich grafów sformułujemy system aksjomatów, którym powinna podlegać miara statusu troficznego. Zauważmy, że w zależności od liczby przyjętych aksjomatów odpowiadająca im miara może być jednoznaczna, niejednoznaczna (przy mniejszej liczbie aksjomatów), a nawet może nie istnieć, jeśli aksjomatów jest zbyt dużo. Odpowiednia liczba aksjomatów z jednej strony prowadzi do barku możliwości wyboru i implikuje jednoznaczność miary, z drugiej — gwarantuje jej istnienie. Jeśli dany układ aksjomatów jest zbyt obszerny i odpowiadająca mu miara nie istnieje, to należy się zastanowić, które z aksjomatów należy usunąć, aby zagwarantować istnienie i jednocześnie nie usunąć zbyt wielu aksjomatów.

Wprowadzając system aksjomatów analogiczny do systemu aksjomatów dla struktury organizacji posłużymy się pojęciami bezpośredniego i pośredniego drapieżnika (analogicznie bezpośredniej i pośredniej ofiary). Powiemy, że gatunek u jest bezpośrednim drapieżnikiem dla v jeśli istnieje krawędź z u do v, natomiast jest pośrednim drapieżnikiem, jeśli v jest osiągalne z u. Będziemy mówić, że u jest drapieżnikiem dla v, jeśli u albo bezpośrednim, albo pośrednim drapieżnikiem dla v. Analogicznie v jest wtedy ofiarą u (bezpośrednią/pośrednią). Zauważmy, że w dowolnym łańcuchu pokarmowym możliwa jest sytuacja, gdy ani u nie jest drapieżnikiem dla v, ani v nie jest drapieżnikiem dla u.

Jeśli u jest drapieżnikiem dla v, to zdefiniujmy

Zauważmy, że powyższa definicja ma sens, gdyż v jest w tym przypadku osiągalne z u, co znaczy, że istnieje najkrótsza ścieżka z u do v, długość której wyznacza odległość z u do v.

Niech tD⁢u oznacza miarę statusu troficznego gatunku u w łańcuchu pokarmowym D. Spełnia ona następujące aksjomaty

[I.]

1. Jeśli gatunek u w łańcuchu D nie jest drapieżnikiem dla żadnego innego gatunku, to tD⁢u=0.

2. Na bazie łańcucha D zbudujmy łańcuch D~ dodając nowy wierzchołek — gatunek, dla którego u jest bezpośrednim drapieżnikiem. Wtedy tD~⁢u>tD⁢u.

3. Na bazie łańcucha D zbudujmy łańcuch D~ dodając wierzchołki lub krawędzie w taki sposób, że dla pewnych gatunków będących drapieżnikami wyróżnionego gatunku u ich status troficzny względem u rośnie, nie ma natomiast takiego gatunku v będącego ofiarą u, dla którego by zmalał. Wtedy tD~⁢u>tD⁢u.

W strukturze organizacji aksjomat I oznacza, że jeśli dany pracownik nie ma żadnych podwładnych, to jego status jest równy 0. W aksjomacie II pracownikowi dajemy nowego bezpośredniego podwładnego, zatem status tego pracownika w organizacji wzrasta. Aksjomat III odzwierciedla sytuację awansu.

Wykażemy teraz istnienie miary spełniającej aksjomaty I – III. Jest to dowód konstrukcyjny. Zdefiniujmy

gdzie nk jest liczbą gatunków na poziomie troficznym k niżej względem u.

Zauważmy, że tak zdefiniowana miara różni się istotnie od proponowanej wcześniej miary reprezentowanej przez poziom troficzny dla drzew. Na rys. 14.3 możemy porównać te dwa pojęcia — korzeń u będący na tym samym poziomie troficznym w obu drzewach ma różny status troficzny ze względu na zróżnicowanie w złożoności tych łańcuchów pokarmowych.

Zauważmy dalej, że hD⁢u≥0, co nie zostało założone w aksjomatach I – III. Jeśli do tych aksjomatów dołożymy postulat nieujemności, to miara hD jest minimalna w następującym sensie

Miara hD ma pewne niepożądane cechy. W szczególności mierząc status troficzny chcielibyśmy mieć następującą własność — jeśli tD jest miarą statusu troficznego i u jest drapieżnikiem dla v, to chcielibyśmy by tD⁢u>tD⁢v. Niestety hD nie ma tej własności, por. rys. 14.4, gdzie u jest bezpośrednim drapieżnikiem dla v i jednocześnie hD⁢u=6<hD⁢v=8.

W celu rozwiązania tego problemu musimy przedefiniować poziom troficzny gatunku u względem gatunku v w łańcuchu pokarmowym. Do tej pory interpretowaliśmy to pojęcie w kontekście odległości od u do v, czyli długości najkrótszej ścieżki, natomiast teraz przedefiniujemy je jako maksymalną długość ścieżki prostej prowadzącej z u do v. Konstruując miarę statusu troficznego w oparciu o to pojęcie dostaniemy funkcję spełniającą aksjomaty I – III i dodatkowo aksjomat

IV. Jeśli gatunek u jest bezpośrednim/pośrednim drapieżnikiem dla v, to tD⁢u>tD⁢v, gdzie tD jest miarą statusu troficznego gatunku u.

Wracając do łańcucha pokarmowego z ostatniego rysunku obliczamy teraz hD⁢u=14>hD⁢v=8.

Miara statusu troficznego pozwala w pewnym sensie zbadać ważność danego gatunku w łańcuchu pokarmowym. Istnieje także inny sposób analizowania roli gatunku w ekosystemie i podatności ekosystemu na zmiany. Opiera się on na pojęciu spójności grafu.

Oczywiście dla grafu nieskierowanego G wszystkie trzy typy spójności pokrywają się, ponieważ ścieżka jest tożsama z pseudościeżką. Wobec tego graf nieskierowany G=V,E jest spójny wtedy i tylko wtedy gdy dla każdej pary wierzchołków u,v∈V istnieje łącząca je ścieżka.

Z podanymi rodzajami spójności wiążemy pojęcie kategorii spójności grafu.

Okazuje się, że poszczególne kategorie spójności są równoważne istnieniu tzw. ścieżek kompletnych.

Na bazie powyższych definicji wprowadzimy kategoryzację wierzchołków.

Dzięki temu pojęciu możemy klasyfikować gatunki w łańcuchu pokarmowym. Za krytyczne w danym ekosystemie uznamy takie gatunki, dla których różnica i-j jest największa, czyli takie, których usunięcie powoduje największą zmianę spójności.

Na koniec omówimy pojęcie wrażliwości na zmiany w danym łańcuchu pokarmowym.

Zauważmy, że im większy stopień podatności, tym graf jest mniej wrażliwy na zmiany.

Podsumowując, dla danego łańcucha pokarmowego jego złożoność i stabilność będzie wyrażać się jak największą liczbą gatunków w ekosystemie z jak największą miarą statusu troficznego i jak największym stopniem podatności.