HyperGraph (HiperGraf, İleri Şekil)
Yazan : Şadi Evren ŞEKER
Bu yazının amacı, hipergraf (ileri şekil, hypergraph) konusunu anlatmaktır. Matematiksel bir terim olan hipergraf kavramı, bilgisayar bilimlerinin çeşitli alanlarında kullanılmaktadır.
Tanım itibariyle bir kenarın (edge) çok sayıdaki düğüme (node) bağlanabildiği özel şekillerdir. Yani, normalde bir şekilde (graph) bir kenar (edge), iki düğüm (node) arasında tanımlıyken ve bu iki düğümü birleştiriyorken, hipergraflarda istenilen sayıdaki düğümü birleştirebilir. Burada istenilen sayı ile kast edilen normal şekillerde olduğu gibi iki düğüm olabilirken tek bir düğüm de olabilir. Normal şekillerde bir kenar tek bir düğüme bağlı olamaz, mutlaka iki düğüme bağlı olmalıdır ama hipergraflarda tek bir düğüme, üç ayrı düğüme veya yirmi ayrı düğüme bağlı olabilir.
Yukarıdaki şekilde, 5 düğüm (node) ve 3 kenar (edge) verilmiştir. Bu şekildeki kenar kümeleri aşağıdaki şekildedir:
K1: { A, B}
K2: { A, C, E}
K3: { A, B, D, E}
Görüldüğü üzere, bir kenar klasik graftan farklı olarak çok sayıda düğüm içerebilmektedir. Bu durumda M adet düğüm ve I adet kenar içeren bir hipergrafın tanımı aşağıdaki şekilde yapılabilir:
H ( D , K)
Buradaki X, düğümler kümesi ve K ise kenarlar kümesidir. Ancak belirtmek gerekir ki K, aslında bir kümeler kümesidir. Yani K’nın her elemanı D’nin alt kümesinden oluşan bir kümedir.
Normal bir şekilde (graph)
G ( D, K)
şeklinde yapılan tanımda, K kümesi ikili elemanlardan oluşan bir kümeyken, bir hiper graf için eleman sayısı asgari 1 ve azami M olan kümelerden oluşan bir kümedir.
Bu durum aşağıdaki şekilde taınmlanabilir:
H ( D , K ) için
Yani diğer bir deyişle, D kümesindeki elemanlar M düğüm için 1’den M’e kadar dm ile gösterilirken, K kümesindeki elemanlar 1’den I’ye kadar ki ile gösterilmektedir. Ayrıca hiper grafın en önemli özelliği olan ki’lerden oluşan küme, D kümesinin herhangi bir alt kümesi olabilir.
Klasik şekillerde (graph) alt şekil (subgraph) tanımı yapılabildiği gibi, hiper graflar için de benzer tanımlamalar yapmak mümkündür. Ancak ancak, hipergraflarda, kenarların belirlediği sayısallık (cardinality) değerleri farklılık gösterdiği için birden fazla alt şekil (subgrah) tanımına ihtiyaç duyulmuştur. Bu tanımlar aşağıda, başlıklar halinde sunulmuştur.
Alt HiperGraf (Sub HyperGraph):
Ayrıca literatürde geçen alt hiper graf ( sub-hypergraph) kavramı, bir hiper grafın düğümlerinin bir kısmının içerilmediği hiper graftır. Örneğin yukarıda verilen hiper grafa H1 diyecek olursak ve bu hipergraftan C düğümünü çıkardığımız yeni hiper grafa H2 diyecek olursak. H2 hipergrafı, H1 hipergrafının bir alt hiper grafıdır denilebilir:
Şekilde görülen yeni hiper graf için kenar kümelerinin yeni tanımı aşağıdaki şekilde olacaktır:
K1: { A, B}
K2: { A, E}
K3: { A, B, D, E}
Bu yeni hipergrafta, normal bir hipergrafın taşıdığı bütün özellikler bulunmaktadır. Buna göre bir althipergraf aşağıdaki şekilde tanımlanabilir:
Yukarıdaki tanımda, normal bir hipergrafın düğümlerini gösteren D kümesinin bir alt kümesi olan A kümesi tanımlanmıştır ( 
) ve buna göre kenarlar kümesi bu A alt kümesinde bulunan düğümleri bir şekilde ilgilendiren alt küme olmaktadır. Öyleki, şayet bu kenarlar alt kümesi DA için boş kümeye dönüşüyorsa, bu küme alınmaz. Yani D kümesinden çıkarılan düğümlerden sonra herhangi bir kenar kümesi boş küme oluyorsa, bu kenar alt hipergrafta bulundurulmaz.
Kısmi HiperGraf (partial hyper graph):
Bir hiper grafın bazı kenarlarının olmadığı hiper graflara verilen isimdir.
Örneğin yukarıdaki yeni hipergrafta, K1 kenarı bulunmamaktadır. Bununla birlikte bütün düğümler (nodes) tam olarak yer almaktadır. Yukarıdaki hiper grafa H3 ismini verecek olursak, H3, H1’in bir kısmi hipergrafıdır denilebilir. Bu hiper grafta bulunan kenar kümeleri aşağıdaki şekilde tanımlanabilir:
K2 = {A, C , E }
K3 = {A, B , D , E}
Bu tanıma göre, şayet 
tanımı yapılırsa,
şeklinde bir kısmi hiper graf tanımlanabilir.
Bölgesel Hiper Graf ( Section Hyper Graph):
Bu kavram, hem kısmi hem de alt hipergraf kavramlarının birleşimidir. Yani hem kenar hem de düğümler, Orijinal hiper grafın alt kümesi olarak kabul edilebilir.
Yukarıdaki şekilde, hem bir düğüm eksik ( C düğümü) hem de bir kenar eksiktir (K1 kenarı) bu durumda bu hiper graf, Orijinal hiper grafın ne kısmi ne de alt hiper grafıdır. Bunun yerine bölgesel hipergrafıdır terimi kullanılır.
İki parçalı graflar (bipartite graph)
Herhangi bir H hipergrafı, iki parçalı graf (bi-partite graph) olarak gösterilebilir. Bunun için D ve K kümelerinin iki parçalı graftaki bölümleri ifade etmesi gerekir.
Herhangi bir düğüm d için, sadece tek bir kenar k tarafından içerilmelidir.