In this thesis, we count and list a special class of directed graphs. We consider directed
graphs which are transitively reduced and do not contain cycles. These directed graphs
have also unique sources and unique sinks. In the text, we called such directed graphs
as “admissible digraphs”. Such directed graphs find applications in bioinformatics and
network flow theory. We constructed explicit algorithms to count and list admissible
digraphs with a specific number of vertices. Our counting algorithm is not exact, it gives
us an upper bound on the number of admissible digraphs with a certain number of vertices.
On the other hand, our listing algorithm is exact and list all admissible digraphs of certain
vertex set size.
Biz bu tezde yönlendirilmiş çizgelerin özel bir sınıfını saymaya ve listelemeye çalıştık.
Göz önünde bulundurduğumuz bu yönlendirilmiş çizgeler geçişli indirgenmişlerdir ve
çevre içermemektedirler. Ayrıca bu yönlendirilmiş çizgeler tek giriş düğümü ve tek çıkış
düğümüne sahiptirler. Bahsettiğimiz yönlendirilmiş çizgeleri metinde “geçerli yönlendirilmiş çizgeler” olarak adlandırdık. Bunların biyoinformatik ve ağ akışı kuramı alanlarında
uygulamaları bulunmaktadır. Düğüm sayıları belirli olan geçerli yönlendirilmiş çizgeleri
saymak ve listelemek için aşikar algoritmalar oluşturduk. Sayma algoritmamız bize kesin
sonuç değil, düğüm sayıları belli olan geçerli yönlendirilmiş çizgelerin sayıları üstünden
üst sınır vermektedir. Buna karşılık, liste algoritmamız bize kesin sonuç vermektedir ve
bütün geçerli yönlendirilmiş çizgeleri düğüm kümesinin boyutu üzerinden listelemektedir.
