Combinatorics and Graph Theory

A Problem on Sum of Powers of Binomial Coefficients

Authors: Suaib Lateef
Comments: 5 pages

In this paper, we present a problem concerning the sum of powers of Binomial coefficients. We prove two special cases of the problem using some simple identities involving Binomial coefficients, and list another two cases but without proof.
Category: Combinatorics and Graph Theory

Introduction to the Theory of Graphs: a Methodological Information Description of the Origem Problem and Applications to the Problem for Solution

Authors: Faustino A. Maciala
Comments: 18 Pages. [Corrections are made by viXra Admin to comply with the rules of viXra.org]

The present work presents a study about the introduction to graph theory,of the problem that originated them and looks at the resolution of some problems that involve it. The first section, the introduction, presents an introductory approach to graph theory, problematization and justification of the choice of theme. In the second section, we present a historical review,its importance and the teaching process learning the same theme adding the concept of graph and different types of graphs. In the third section, Results and Discussion, we present the problem of bridges in the city of K ̈onigsbergand some application problems, such as color or 4-color problem, telephone calls and Minimum Longitude Path.

O presente trabalho traz um estudo sobre a introdução a teoria de grafos, do problema que os originou e faz um olhar a resolução de alguns problemas que o envolvem. A primeira secção, a introdução, faz-se uma abordagem introdutória da teoria de grafos, da problematização e da justicativa da escolha do tema. Na segunda secção, apresentamos uma resenha histórica, sua importância e o processo de ensino aprendizagem do mesmo tema acrescendo o conceito de grafo e diferentes tipos de grafos. Na terceira secção, resultados e Discussão, apresenta-se o problema das pontes de Na cidade de Khonigsberg e apresenta-se alguns problemas de aplicação, tais como, problema de coloração ou das 4 cores, chamadas telefónicas e Caminho de Longitude Mínima. Palavras Chave: Grafos, Teoria de Grafos e Resolução de Problemas.
Category: Combinatorics and Graph Theory

Combinatorial Optimization Problem Solving Method by Correlation Coefficient of Ising Model Order Parameter

Authors: Akira Saito
Comments: 4 Pages.

任意の相互作用パラメータを持つイジングモデルの秩序変数を相関係数で表すことができた。これにより検定力分析で決まるサンプル数によって、ある精度の条件下で、秩序変数を求めることができる。温度0でのイジングモデルの秩序変数は、組み合わせ最適化問題の解となることが知られている。各秩序変数によりyesなのかnoなのかを知りたいだけであれば、サンプル数で求まる秩序変数で判断することができる。つまり、組み合わせ最適化問題を、計算ステップ数 T 、入力サイズ N に対してT∼O(N^k)で解くことができる可能性がある。このことはNP困難問題を多項式時間で解ける可能性を示しており、P=NPを暗示している。
Category: Combinatorics and Graph Theory

New Insight Into Introducing a (2-ℇ)-Approximation Ratio for Minimum Vertex Cover Problem

Authors: Majid Zohrehbandian
Comments: 9 Pages.

Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied over the years and it is known that there is not any mathematical programming formulation that approximates it better than 2-o(1), while a 2-approximation for it can be trivially obtained. In this paper, by a combination of a well-known semidefinite programming formulation and a randomized procedure, along with satisfying new properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of 1.999999 on arbitrary graphs, en route to answering an open question about the unique games conjecture.
Category: Combinatorics and Graph Theory