Tranzitivna redukcija
From Wikipedia, the free encyclopedia
U matematici, tranzitivna redukcija usmerenog grafa je graf sa nekoliko grana koliko je moguće tako da imaju isti odnos dosega kao dati graf. Podjednako, dati graf i njegova tranzitivna redukcija trebalo bi da imaju ista tranzitivna zatvorenja, i njihove tranzitivne redukcije bi trebalo da imaju nekoliko grana koliko je to moguće među svim grafovima ovih osobina. Tranzitivne redukcije je uveo Aho, Garey & Ullman 1972, koji je uveo tanke granice pri njihovom složenom računarskom konstruisanju.
Ako je dati graf konačan usmeren acikličan garaf, njegova tranzitivna redukcija je jedinstvena, i podgraf je datog grafa. Međutim jedinstvenost nije garancija za ciklične grafove, i za beskonačne grafove postojanje uopšte nije ni garantovano.Blisko povezani koncepti minimalnog ekvivalentnog grafa je podgraf datog grafa koji ima istu relaciju dosega i što je moguće manje konačne usmerene aciklične grafove, minimalni ekvivalentni graf je isti kao i tranzitivna redukcija. Međutim, za ciklične grafove, minimalni ekvivalentan graf se NP-teško konstruiše, dok se tranzitivna redukcija i dalje može konstruisati u polinomijalnom vremenu.Tranzitivna redukcija se takođe može definisati za abstraktnije binarne relacije skupova, pretstavljanjem parova relacija kao grana grafa.