Balinski sætning

I polyhedrale kombinatorik, en gren af ​​matematikken, Balinski sætning er en erklæring om grafen-teoretiske struktur af tre-dimensionelle polyedre og højere-dimensionale polyedre. Det hedder, at hvis man er en ikke-orienteret graf fra de hjørner og kanter af en konveks d-dimensional polyeder eller polytope, så den resulterende graf er mindst d-knude-tilsluttet: fjernelse af enhver d - 1 knuder efterlader en tilsluttet delgraf . For eksempel, for et tredimensionalt polyeder, selv om to af dets knudepunkter fjernes, for ethvert par af knuder vil der stadig findes en sti af knuder og kanter, der forbinder parret.

Balinski sætning er opkaldt efter matematikeren Michel Balinski, som offentliggjorde sin bevis i 1961, selv om den tredimensionale tilfælde går tilbage til den tidligere del af det 20. århundrede og opdagelsen af ​​Steinitz sætning, at graferne for tre-dimensionelle polyedre er nøjagtigt de tre -connected plane grafer.

Balinski s bevis

Balinski beviser resultat baseret på rigtigheden af ​​simplex metode til at finde minimum eller maksimum en lineær funktion på en konveks polytop. Simplexmetoden starter ved en vilkårlig toppunkt af polytope og gentagne gange bevæger sig i retning en tilstødende toppunkt, der forbedrer funktionen værdi; når ingen forbedring kan ske, har den optimale funktionsværdi er nået.

Hvis S er et sæt af færre end d knudepunkter, der skal fjernes fra grafen for polytope, Balinski tilføjer endnu et toppunkt v0 til S og finder en lineær funktion ƒ, der har værdien nul på den forstærkede sæt, men ikke er identisk nul på hele rummet. Derefter kan eventuelle resterende toppunkt ved hvilken ƒ er ikke-negative forbindes ved simplex trin til toppunktet med den maksimale værdi af ƒ, mens resterende toppunkt ved hvilken ƒ er kraftsluttende kan tilsvarende forbundet til toppunktet med den mindste værdi af ƒ. Derfor er hele den resterende graf tilsluttet.

  0   0

Relaterede Artikler

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha