On One Class of Undirected Graph

Kochkarev Bagram; Sibgatullovich

doi:doi:10.11648/j.cse.20170101.11

| Peer-Reviewed

On One Class of Undirected Graph

Kochkarev Bagram, Sibgatullovich

Published in Control Science and Engineering (Volume 1, Issue 1)

Received: 1 April 2017 Accepted: 18 April 2017 Published: 31 May 2017

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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

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

Plain Text BibTeX RIS

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

Kochkarev Bagram

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

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

Download PDF

Sections

Plain Text BibTeX RIS

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