BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Perz Szczepan
Tytuł
O pewnych związkach programowania liniowego z teorią liczb i teorią grafów
On Some Relations Between Linear Programming, Number Theory and Graph Theory
Źródło
Przegląd Statystyczny, 2003, vol. 50, z. 2, s. 133-157, bibliogr. 20 poz.
Statistical Review
Słowa kluczowe
Programowanie liniowe, Teoria grafów, Teoria liczb
Linear programming, Graph theory, Number theory
Uwagi
summ.
Abstrakt
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.

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.
Dostępne w
Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie
Biblioteka Szkoły Głównej Handlowej w Warszawie
Biblioteka Główna Uniwersytetu Ekonomicznego w Katowicach
Biblioteka Główna Uniwersytetu Ekonomicznego w Poznaniu
Biblioteka Główna Uniwersytetu Ekonomicznego we Wrocławiu
Bibliografia
Pokaż
  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.
Cytowane przez
Pokaż
ISSN
0033-2372
Język
pol
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu