| Peer-Reviewed

On One Class of Undirected Graph

Received: 1 April 2017     Accepted: 18 April 2017     Published: 31 May 2017
Views:       Downloads:
Abstract

Introduced the concept of polynomial combinatorial sets in enumerative combinatorics and formulates the problem of finding some element with an easily recognized symptom among elements of a combinatorial set. We build an efficient algorithm to solve this problem. We prove that this algorithm does not fit into the formal definition of an algorithm (e.g. “Turing machine”). It is proved that all NP-complete problems are not polynomial. We consider a countable class of undirected Hamiltonian graphs with an odd number of vertices without loops and multiple edges. We prove one typical feature of such graphs: almost every simple path containing all the vertices of the graph is not Hamiltonian cycle. In other words, in the langage of probability theory, the probability that a randomly selected a simple path in this graph containing all vertices, is Hamiltonian cycle tends to zero with growth of number vertices.

Published in Control Science and Engineering (Volume 1, Issue 1)
DOI 10.11648/j.cse.20170101.11
Page(s) 1-3
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2017. Published by Science Publishing Group

Previous article
Keywords

An Undirected Graph, A Simple Path, Hamiltonian Cycle, Polynomial Combinatorial Set, Non-polynomial Combinatorial Set

References
[1] Kochkarev B. S. Gipoteza J. Edmondsa I problema S. A. Kuka //Vestnik TGGPU, 2011 2 (24) s. 23-24 (in Russian).
[2] Kochkarev B. S. On Cook’s problem. http://www.math.nsc.ru/conference/.
[3] Kochkarev B. S. Prilogenie monotonnykh funktsii algebry logiki k probleme Kuka, Nauka v Vuzakh: matematika, fizika, informatika. Tezisy dokladov Mejdunarodnoj nauchno-obrazovatelnoj konferentsii, 2009, pp274-275 (in Russian).
[4] Kochkarev B. S. About one class polynomial problems with not polynomial certificates //arXiv: 1210. 7591v1 [math. CO] 29 Oct. 2012.
[5] Kochkarev B. S. Proof of the hypothesis Edmonds’s, not polynomial of NPC problems and classification of the problems with polynomial certificates. //arXiv: 1303. 2580v1 [cs. CC] Mar 2013.
[6] Kochkarev B. S. Typical property of one class of combinatory objects and estimatin from above corresponding combinatory numbers //arXiv: 1304. 4363v1 [cs. DM] 16Apr 2013.
[7] Kochkarev B. S. About one class polynomial problems with not polynomial certificates //Second International Conference “Claster Computing” CC 2013 (Ukraine, Lviv, June 3-5, 2013) P. 99-100.
[8] Kochkarev B. S. Dokazatelstvo gipotezy Edmondsa I reshenie problem Kuka. Nauka, Tekhnika I Obrazovanie, 2014, 2 (2) s. 6-9 (in Russian).
[9] Kochkarev B. S. Vzaimootnosheniya mejdu slojnostnymi klassami P, NPi NPC Problems of modern science and education. 2015, 11(41). S. 6-8 (in Russian).
[10] Kochkarev B. S. Problem of Recognition of Hamiltonian Graph //International Journal of Wirless Communication and Mobile Computing 2016; 4 (2): 52-55.
[11] Kochkarev B. S. Typical Properties of Maximal Sperner Families of Type (k, k+1) and Upper Esnimate. //IOSR Journal of Mathematics (IOSR-JM) Volum 13, Issue 2 Ver II (Mar-Apr. 2017) PP. 16-23.
[12] Wiles A. Modular elliptic curves and Fermat’s Last Theorem Annals of Mathematics. V. 141 Second series 3 May 1995 pp. 445-551.
[13] Kochkarev B. S. Ob odnom klasse algebraicheskikh uravnenij, ne imejutshikh ratsionalnykh reshenij //Problem of moden science and education. 2014. 4(22) s. 9-11.
[14] Kochkarev B. S. Algorithm of search of Large Prime Numbers //International Journal of Discrete Mathematics, 2016; 1 (1): 30-32.
[15] Kochkarev B. S. About One Binary Problem in a class of algebraic equations and Her Communication with The Great Hypothesis of Fermat //International Journal of Current Multidisciplinary Studies Vol. 2, Issue, 10, pp. 457-459, October, 2016.
[16] Stanley R. P. Enumerative Combinatorics v. 1, 1986.
[17] Yablonsky S. V. Vvedenie v diskretnuyu matematiku Moskow, 1986, P. 384.
[18] Cormen T. H., Ch. E. Leiserson, Rivest R. L. Algoritmy, postroenie I analiz, 2002, MTSNMO, Moskow P. 960.
[19] Ravenstvo klassov P i NP https://ru.wikipedia.org/wiki
[20] Karp R. M. Reducibility among combinatorial problems. //In Raymond E, Miller and James W. Thatcher, editors, Complexity of computer Computations, P. 85-103, Plenum Press, 1972.
Cite This Article
  • APA Style

    Kochkarev Bagram, Sibgatullovich. (2017). On One Class of Undirected Graph. Control Science and Engineering, 1(1), 1-3. https://doi.org/10.11648/j.cse.20170101.11

    Copy | Download

    ACS Style

    Kochkarev Bagram; Sibgatullovich. On One Class of Undirected Graph. Control Sci. Eng. 2017, 1(1), 1-3. doi: 10.11648/j.cse.20170101.11

    Copy | Download

    AMA Style

    Kochkarev Bagram, Sibgatullovich. On One Class of Undirected Graph. Control Sci Eng. 2017;1(1):1-3. doi: 10.11648/j.cse.20170101.11

    Copy | Download

  • @article{10.11648/j.cse.20170101.11,
      author = {Kochkarev Bagram and Sibgatullovich},
      title = {On One Class of Undirected Graph},
      journal = {Control Science and Engineering},
      volume = {1},
      number = {1},
      pages = {1-3},
      doi = {10.11648/j.cse.20170101.11},
      url = {https://doi.org/10.11648/j.cse.20170101.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.cse.20170101.11},
      abstract = {Introduced the concept of polynomial combinatorial sets in enumerative combinatorics and formulates the problem of finding some element with an easily recognized symptom among elements of a combinatorial set. We build an efficient algorithm to solve this problem. We prove that this algorithm does not fit into the formal definition of an algorithm (e.g. “Turing machine”). It is proved that all NP-complete problems are not polynomial. We consider a countable class of undirected Hamiltonian graphs with an odd number of vertices without loops and multiple edges. We prove one typical feature of such graphs: almost every simple path containing all the vertices of the graph is not Hamiltonian cycle. In other words, in the langage of probability theory, the probability that a randomly selected a simple path in this graph containing all vertices, is Hamiltonian cycle tends to zero with growth of number vertices.},
     year = {2017}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - On One Class of Undirected Graph
    AU  - Kochkarev Bagram
    AU  - Sibgatullovich
    Y1  - 2017/05/31
    PY  - 2017
    N1  - https://doi.org/10.11648/j.cse.20170101.11
    DO  - 10.11648/j.cse.20170101.11
    T2  - Control Science and Engineering
    JF  - Control Science and Engineering
    JO  - Control Science and Engineering
    SP  - 1
    EP  - 3
    PB  - Science Publishing Group
    SN  - 2994-7421
    UR  - https://doi.org/10.11648/j.cse.20170101.11
    AB  - Introduced the concept of polynomial combinatorial sets in enumerative combinatorics and formulates the problem of finding some element with an easily recognized symptom among elements of a combinatorial set. We build an efficient algorithm to solve this problem. We prove that this algorithm does not fit into the formal definition of an algorithm (e.g. “Turing machine”). It is proved that all NP-complete problems are not polynomial. We consider a countable class of undirected Hamiltonian graphs with an odd number of vertices without loops and multiple edges. We prove one typical feature of such graphs: almost every simple path containing all the vertices of the graph is not Hamiltonian cycle. In other words, in the langage of probability theory, the probability that a randomly selected a simple path in this graph containing all vertices, is Hamiltonian cycle tends to zero with growth of number vertices.
    VL  - 1
    IS  - 1
    ER  - 

    Copy | Download

Author Information
  • Department of Mathematics and Mathematical Modelling, Institute of Mathematics and Mechanics Named After N. I. Lobachevsky, Kazan (Volga Region) Federal University, Kazan, Russia

  • Department of Mathematics and Mathematical Modelling, Institute of Mathematics and Mechanics Named After N. I. Lobachevsky, Kazan (Volga Region) Federal University, Kazan, Russia

  • Sections