Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "polytope" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-12 z 12
    Tytuł:
    Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem
    Autorzy:
    Sierksma, Gerard
    Powiązania:
    https://bibliotekanauki.pl/articles/1340570.pdf
    Data publikacji:
    1994
    Wydawca:
    Polska Akademia Nauk. Instytut Matematyczny PAN
    Tematy:
    Assignment Polytope
    Traveling Salesman Polytope
    Opis:
    The 3-Opt procedure deals with interchanging three edges of a tour with three edges not on that tour. For n≥6, the 3-Interchange Graph is a graph on 1/2(n-1)! vertices, corresponding to the hamiltonian tours in K_n; two vertices are adjacent iff the corresponding hamiltonian tours differ in an interchange of 3 edges; i.e. the tours differ in a single 3-Opt step. It is shown that the 3-Interchange Graph is a hamiltonian subgraph of the Symmetric Traveling Salesman Polytope. Upper bounds are derived for the diameters of the 3-Interchange Graph and the union of the 2- and the 3-Interchange Graphs. Finally, some new adjacency properties for the Asymmetric Traveling Salesman Polytope and the Assignment Polytope are given.
    Źródło:
    Applicationes Mathematicae; 1993-1995, 22, 3; 351-358
    1233-7234
    Pojawia się w:
    Applicationes Mathematicae
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Describing Neighborhoods of 5-Vertices in 3-Polytopes with Minimum Degree 5 and Without Vertices of Degrees from 7 to 11
    Autorzy:
    Borodin, Oleg V.
    Ivanova, Anna O.
    Kazak, Olesya N.
    Powiązania:
    https://bibliotekanauki.pl/articles/31342287.pdf
    Data publikacji:
    2018-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    planar graph
    structure properties
    3-polytope
    neighborhood
    Opis:
    In 1940, Lebesgue proved that every 3-polytope contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: (6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11), (5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17), (5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6, ∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11), (5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13). In this paper we prove that every 3-polytope without vertices of degree from 7 to 11 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6), where all parameters are tight.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 3; 615-625
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    An inequality concerning edges of minor weight in convex 3-polytopes
    Autorzy:
    Fabrici, Igor
    Jendrol', Stanislav
    Powiązania:
    https://bibliotekanauki.pl/articles/972043.pdf
    Data publikacji:
    1996
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    planar graph
    convex 3-polytope
    normal map
    Opis:
    Let $e_{ij}$ be the number of edges in a convex 3-polytope joining the vertices of degree i with the vertices of degree j. We prove that for every convex 3-polytope there is $20e_{3,3} + 25e_{3,4} + 16e_{3,5} + 10e_{3,6} + 6[2/3]e_{3,7} + 5e_{3,8} + 2[1/2]e_{3,9} + 2e_{3,10} + 16[2/3]e_{4,4} + 11e_{4,5} + 5e_{4,6} + 1[2/3]e_{4,7} + 5[1/3]e_{5,5} + 2e_{5,6} ≥ 120$; moreover, each coefficient is the best possible. This result brings a final answer to the conjecture raised by B. Grünbaum in 1973.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1996, 16, 1; 81-87
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5
    Autorzy:
    Borodin, Oleg V.
    Ivanova, Anna O.
    Powiązania:
    https://bibliotekanauki.pl/articles/31342193.pdf
    Data publikacji:
    2017-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    3-polytope
    planar graph
    structure properties
    k -star
    Opis:
    Lebesgue (1940) proved that every 3-polytope P5 of girth 5 has a path of three vertices of degree 3. Madaras (2004) refined this by showing that every P5 has a 3-vertex with two 3-neighbors and the third neighbor of degree at most 4. This description of 3-stars in P5s is tight in the sense that no its parameter can be strengthened due to the dodecahedron combined with the existence of a P5 in which every 3-vertex has a 4-neighbor. We give another tight description of 3-stars in P5s: there is a vertex of degree at most 4 having three 3-neighbors. Furthermore, we show that there are only these two tight descriptions of 3-stars in P5s. Also, we give a tight description of stars with at least three rays in P5s and pose a problem of describing all such descriptions. Finally, we prove a structural theorem about P5s that might be useful in further research.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 1; 5-12
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7
    Autorzy:
    Batueva, Ts.Ch-D.
    Borodin, O.V.
    Ivanova, A.O.
    Nikiforov, D.V.
    Powiązania:
    https://bibliotekanauki.pl/articles/32361718.pdf
    Data publikacji:
    2022-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    planar graph
    structural properties
    3-polytope
    5-star
    neighborhood
    Opis:
    In 1940, in attempts to solve the Four Color Problem, Henry Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P5 of 3-polytopes with minimum degree 5. This description depends on 32 main parameters. (6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11), (5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17), (5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6, ∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11), (5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13) Not many precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in P5. In 2018, Borodin, Ivanova, Kazak proved that every forbidding vertices of degree from 7 to 11 results in a tight description (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6). Recently, Borodin, Ivanova, and Kazak proved every 3-polytope in P5 with no vertices of degrees 6, 7, and 8 has a 5-vertex whose neighborhood is majorized by one of the sequences (5, 5, 5, 5, ∞) and (5, 5, 10, 5, 12), which is tight and improves a corresponding description (5, 5, 5, 5, ∞), (5, 5, 9, 5, 17), (5, 5, 10, 5, 14), (5, 5, 11, 5, 13) that follows from the Lebesgue Theorem. The purpose of this paper is to prove that every 3-polytope with minimum degree 5 and no vertices of degree 6 or 7 has a 5-vertex whose neighborhood is majorized by one of the ordered sequences (5, 5, 5, 5, ∞), (5, 5, 8, 5, 14), or (5, 5, 10, 5, 12).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 2; 535-548
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the Weight of Minor Faces in Triangle-Free 3-Polytopes
    Autorzy:
    Borodin, Oleg V.
    Ivanova, Anna O.
    Powiązania:
    https://bibliotekanauki.pl/articles/31340872.pdf
    Data publikacji:
    2016-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    plane map
    plane graph
    3-polytope
    structural property
    weight of face
    Opis:
    The weight w(f) of a face f in a 3-polytope is the degree-sum of vertices incident with f. It follows from Lebesgue’s results of 1940 that every triangle-free 3-polytope without 4-faces incident with at least three 3-vertices has a 4-face with w ≤ 21 or a 5-face with w ≤ 17. Here, the bound 17 is sharp, but it was still unknown whether 21 is sharp. The purpose of this paper is to improve this 21 to 20, which is best possible.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 3; 603-619
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    More About the Height of Faces in 3-Polytopes
    Autorzy:
    Borodin, Oleg V.
    Bykov, Mikhail A.
    Ivanova, Anna O.
    Powiązania:
    https://bibliotekanauki.pl/articles/31342325.pdf
    Data publikacji:
    2018-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    plane map
    planar graph
    3-polytope
    structural properties
    height of face
    Opis:
    The height of a face in a 3-polytope is the maximum degree of its incident vertices, and the height of a 3-polytope, h, is the minimum height of its faces. A face is pyramidal if it is either a 4-face incident with three 3-vertices, or a 3-face incident with two vertices of degree at most 4. If pyramidal faces are allowed, then h can be arbitrarily large, so we assume the absence of pyramidal faces in what follows. In 1940, Lebesgue proved that every quadrangulated 3-polytope has h ≤ 11. In 1995, this bound was lowered by Avgustinovich and Borodin to 10. Recently, Borodin and Ivanova improved it to the sharp bound 8. For plane triangulation without 4-vertices, Borodin (1992), confirming the Kotzig conjecture of 1979, proved that h ≤ 20, which bound is sharp. Later, Borodin (1998) proved that h ≤ 20 for all triangulated 3-polytopes. In 1996, Horňák and Jendrol’ proved for arbitrarily polytopes that h ≤ 23. Recently, Borodin and Ivanova obtained the sharp bounds 10 for trianglefree polytopes and 20 for arbitrary polytopes. In this paper we prove that any polytope has a face of degree at most 10 with height at most 20, where 10 and 20 are sharp.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 2; 443-453
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Light Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No 6-Vertices
    Autorzy:
    Borodin, Oleg V.
    Ivanova, Anna O.
    Vasil’eva, Ekaterina I.
    Powiązania:
    https://bibliotekanauki.pl/articles/31348169.pdf
    Data publikacji:
    2020-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    planar map
    planar graph
    3-polytope
    structural properties
    5-star
    weight
    height
    Opis:
    In 1940, Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P5 of 3-polytopes with minimum degree 5. Given a 3-polytope P, by w(P) denote the minimum of the degree-sum (weight) of the neighborhoods of 5-vertices (minor 5-stars) in P. In 1996, Jendrol’ and Madaras showed that if a polytope P in P5 is allowed to have a 5-vertex adjacent to four 5-vertices, then w(P) can be arbitrarily large. For each P in P5 without vertices of degree 6 and 5-vertices adjacent to four 5-vertices, it follows from Lebesgue’s Theorem that w(P) ≤ 68. Recently, this bound was lowered to w(P) ≤ 55 by Borodin, Ivanova, and Jensen and then to w(P) ≤ 51 by Borodin and Ivanova. In this note, we prove that every such polytope P satisfies w(P) ≤ 44, which bound is sharp.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 4; 985-994
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Low 5-Stars at 5-Vertices in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree from 7 to 9
    Autorzy:
    Borodin, Oleg V.
    Bykov, Mikhail A.
    Ivanova, Anna O.
    Powiązania:
    https://bibliotekanauki.pl/articles/31348144.pdf
    Data publikacji:
    2020-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    planar map
    planar graph
    3-polytope
    structural properties
    5-star
    weight
    height
    Opis:
    In 1940, Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class $P_5$ of 3-polytopes with minimum degree 5. Given a 3-polytope $P$, by $h_5(P)$ we denote the minimum of the maximum degrees (height) of the neighborhoods of 5-vertices (minor 5-stars) in $P$. Recently, Borodin, Ivanova and Jensen showed that if a polytope $P$ in $P_5$ is allowed to have a 5-vertex adjacent to two 5-vertices and two more vertices of degree at most 6, called a (5, 5, 6, 6, ∞)-vertex, then $h_5(P)$ can be arbitrarily large. Therefore, we consider the subclass \(P_5^\ast\) of 3-polytopes in $P_5$ that avoid (5, 5, 6, 6, ∞)-vertices. For each $P^\ast$ in $P_5^\ast$ without vertices of degree from 7 to 9, it follows from Lebesgue’s Theorem that $h_5(P^\ast) ≤ 17$. Recently, this bound was lowered by Borodin, Ivanova, and Kazak to the sharp bound $h_5(P^\ast) ≤ 15$ assuming the absence of vertices of degree from 7 to 11 in $P^\ast$. In this note, we extend the bound $h_5(P^\ast) ≤ 15$ to all $P^\ast$s without vertices of degree from 7 to 9.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 4; 1025-1033
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Core Index of Perfect Matching Polytope for a 2-Connected Cubic Graph
    Autorzy:
    Wang, Xiumei
    Lin, Yixun
    Powiązania:
    https://bibliotekanauki.pl/articles/31343794.pdf
    Data publikacji:
    2018-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Fulkerson’s conjecture
    Fan-Raspaud conjecture
    cubic graph
    perfect matching polytope
    core index
    Opis:
    For a 2-connected cubic graph $G$, the perfect matching polytope $P(G)$ of $G$ contains a special point \( x^c = ( \tfrac{1}{3},\tfrac{1}{3},…,\tfrac{1}{3}) \). The core index $ \phi(P(G)) $ of the polytope $P(G)$ is the minimum number of vertices of $P(G)$ whose convex hull contains $ x^c$. The Fulkerson’s conjecture asserts that every 2-connected cubic graph $G$ has six perfect matchings such that each edge appears in exactly two of them, namely, there are six vertices of $P(G)$ such that $ x^c $ is the convex combination of them, which implies that $ \phi(P(G)) \le 6 $. It turns out that the latter assertion in turn implies the Fan-Raspaud conjecture: In every 2-connected cubic graph $G$, there are three perfect matchings $M_1$, $M_2$, and $M_3$ such that $M_1 \cap M_2 \cap M_3 = \emptyset $. In this paper we prove the Fan-Raspaud conjecture for $ \phi(P(G)) \le 12 $ with certain dimensional conditions.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 1; 189-201
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Regularized nonnegative matrix factorization: Geometrical interpretation and application to spectral unmixing
    Autorzy:
    Zdunek, R.
    Powiązania:
    https://bibliotekanauki.pl/articles/329732.pdf
    Data publikacji:
    2014
    Wydawca:
    Uniwersytet Zielonogórski. Oficyna Wydawnicza
    Tematy:
    blind source separation
    nonnegative matrix factorization
    active set algorithm
    regularized NMF
    polytope approximation
    ślepa separacja sygnału
    nieujemna faktoryzacja macierzy
    Opis:
    Nonnegative Matrix Factorization (NMF) is an important tool in data spectral analysis. However, when a mixing matrix or sources are not sufficiently sparse, NMF of an observation matrix is not unique. Many numerical optimization algorithms, which assure fast convergence for specific problems, may easily get stuck into unfavorable local minima of an objective function, resulting in very low performance. In this paper, we discuss the Tikhonov regularized version of the Fast Combinatorial NonNegative Least Squares (FC-NNLS) algorithm (proposed by Benthem and Keenan in 2004), where the regularization parameter starts from a large value and decreases gradually with iterations. A geometrical analysis and justification of this approach are presented. The numerical experiments, carried out for various benchmarks of spectral signals, demonstrate that this kind of regularization, when applied to the FC-NNLS algorithm, is essential to obtain good performance.
    Źródło:
    International Journal of Applied Mathematics and Computer Science; 2014, 24, 2; 233-247
    1641-876X
    2083-8492
    Pojawia się w:
    International Journal of Applied Mathematics and Computer Science
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Structure of the set of all minimal total dominating functions of some classes of graphs
    Autorzy:
    Kumar, K.
    MacGillivray, Gary
    Powiązania:
    https://bibliotekanauki.pl/articles/744030.pdf
    Data publikacji:
    2010
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    minimal total dominating functions (MTDFs)
    convex combination of MTDFs
    basic minimal total dominating functions (BMTDFs)
    simplex
    polytope
    simplicial complex
    function separable graphs
    function reducible graphs
    Opis:
    In this paper we study some of the structural properties of the set of all minimal total dominating functions ($_T$) of cycles and paths and introduce the idea of function reducible graphs and function separable graphs. It is proved that a function reducible graph is a function separable graph. We shall also see how the idea of function reducibility is used to study the structure of $_T(G)$ for some classes of graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2010, 30, 3; 407-423
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-12 z 12

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies