Optimisasi Kombinatorial dengan 2 Join

Abstract

A 2 join is a generalization of 1 join and an edge cutset that naturally appears in decomposition of several classes of graph closed under taking from induced subgraph. A 2 join is used for combinatorial optimization problem solving polynomial time and contribute to the end on the composition characteristics. Not all of the graph have 2 join it will be given an algorithm to detect the presence of 2 join on a graph that is focused on 4-tuple. Graph that can be detected to have 2 join a connected graph can be partitioned.

Sebuah 2 join merupakan generalisasi dari 1 join dan merupakan edge cutset yang muncul secara alami dari dekomposisi beberapa kelas graf tertutup yang diambil dari induced subgraf. Sebuah 2 join digunakan untuk penyelesaian masalah opti- misasi kombinatorial waktu polinomial dan berperan sampai akhir pada susunan karakteristik. Tidak semua graf memiliki 2 join maka akan dberikan algoritma untuk mendeteksi adanya 2 join pada sebuah graf yang difokuskan untuk 4-tuple. Graf yang dapat dideteksi memiliki 2 join merupakan graf bipartisi.