O pewnych związkach programowania liniowego z teorią liczb i teorią grafów

• Autorzy: Szczepan Perz

Warianty tytułu

On Some Relations Between Linear Programming, Number Theory and Graph Theory

• Języki publikacji: PL

Abstrakty

Przedmiotem artykułu jest słabe i mocne przypuszczenie C. Berga o grafach doskonałych. Autor przedstawia dowody tych przypuszczeń przeprowadzone z wykorzystaniem metod analizy funkcjonalnej, teorii liczb i programowania liniowego.

EN

In the graph theory there are two hypothesis (weak and strong) of C. Berg concerning perfect graphs. In this paper, the weak hypothesis, proved with combinatory methods by Laszlo Lovasz, has been reinterpreted (which is the construction made with the author's cooperation). That interpretation concerns the relation between the hypothesis and duality of some forms in Rn. Then we present alternative proof of the hypothesis with use of the functional analysis methods. The strong hypothesis (still - for 40 years - unproved) deals with the minimal imperfect hypergraphs. This paper tries to put into algebraic form the strong Berg's hypothesis. The norms, which do not fulfill the positive homogeneity condition, defined in the Zn space over the ring of integers Z, determine some ideals in the Z ring. The author formulate the hypothesis that for every pair of imperfect minimal hypergraphs one can find some maximal ideal of the ring Z, that is some prime number. The derivation of the norm's value (for which the unit ball is a polyhedron) for a given vector can be thought of as a specific task of linear programming. This task can be solved by border matrices technique with use of simplex method.

Słowa kluczowe

PL

Programowanie liniowe; Teoria grafów; Teoria liczb

EN

Linear programming; Graph theory; Number theory

• Czasopismo: Przegląd Statystyczny
• Rocznik: 2003
• Tom: 50
• Numer: z. 2
• Strony: 133--157

Twórcy

autor

Szczepan Perz

Bibliografia

• [1] Alexiewicz A., Analiza funkcjonalna, PWN Warszawa 1977.
• [2] Balakrishnan A.V., Analiza funkcjonalna stosowana, PWN, Warszawa 1992.
• [3] Berge C. and Duchet P., Strongly perfect graphs In "Topics on Perfect Graphs". (C. Berge and V. Chwa-tal, Eds.) Ann. Discrete Math. 21, 1984, s. 57-61.
• [4] Berge C., Graphs and hypergraphs, North Holland Publishing Company, 1976.
• [5] Białynicki-Birula A., Zarys Algebry, PWN, Warszawa 1987.
• [6] Bland R.G., Huang H.C. and Trotter L.E. Jr., Graphical properties related to minimal imperfection, Discrete Math. 27, 1979, s. 11-22.
• [7] Browkin J., Teoria Ciał, PWN, Warszawa 1977.
• [8] Gale D., Teoria linowych modeli, C.
• [9] Golumbic M.C., Algorithmic graph theory and perfect graphs, Academic Press, New York 1980.
• [10] Kolupa M., Teoria Ekonometria z wykorzystaniem macierzy brzegowych, wydawnictwo Wyższej Szkoły Przedsiębiorczości i Zarządzania, Warszawa, 1998.
• [11] Lang S., Algebra, PWN, Warszawa 1984.
• [12] Lipski W, Marek W, Analiza kombinatoryczna Academic, PWN, Warszawa 1971.
• [13] Lovasz L., Normal hypergraphs and perfect graph conjecture, Discrete Math. 2, 1972, s. 253-267.
• [14] Mirsky L., Transversal Theory, Academic Press, New York 1971.
• [15] Perz Sz. and Rolewicz St., Norms and Perfect Graphs, ZOR - Methods and Models of Operations Research, 1990, s. 13-27.
• [16] Rolewicz St., Analiza funkcjonalna i teoria sterowania, PWN, Warszawa 1977.
• [17] Sułtan P.S., Wwiedienije w aksjomaticzieskuju tieoriju wypuklosti, Sztinca, Kiszyniów 1986.
• [18] Wagner H.M., Badania Operacyjne, PWE, Warszawa 1980.
• [19] Walukiewicz St., Programowanie dyskretne, PWN, Warszawa 1986.
• [20] Zaremba L.S. and Perz Sz., On a Geometric Property of Perfect Graphs, Combinatorica 2(4), 1982, s. 395-397.