Hipergrafeo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
Ekzemplo de hipergrafeo kun V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}, E= \{e_1,e_2,e_3,e_4\} =\{\{v_1, v_2, v_3\}, \{v_2,v_3\}, \{v_3,v_5,v_6\},\{v_4\}\}.

En matematiko, hipergrafeo estas aro (V,E), kie V estas aro de elementoj (nomataj kiel verticoj) kaj E estas aro de subaroj de V (nomataj eĝoj aŭ, pli precize, hipereĝoj).

Hipergrafeo do estas ĝeneraligo de ordinara grafeo, kie eĝoj povas ligi pli ol du verticojn. Tiel hipereĝo estas ĝeneraligo de eĝo al ajna kvanto de la enhavataj verticoj.

Se ĉiu hipereĝo konsistas el k elementoj, la hipergrafeo nomiĝas k-unuforma, aŭ simple k-grafeo. Ordinara grafeo do estas 2-unuforma hipergrafeo2-grafeo.

Literaturo[redakti | redakti fonton]

  • Matthias, Ulrich: Rifuto de kombinatorika konjekto de P. Turán, Scienca Revuo Vol. 45 (1994)(2), p. 26-30.