\displaystyle f(G) = (k,G) gdzie k = \sum_{e \in E(G)} waga(e) + 1
Problem komiwojażera, to pytanie, czy istnieje cykl Hamiltona o wadze mniejszej niż k. Potrafimy tym rozwiązać pytanie o jakikolwiek cykl Hamiltona, jeżeli damy dobre ograniczenie górne. Tutaj tym ograniczeniem jest suma wag krawędzi (każdy cykl Hamiltona nigdy nie będzie miał w sumie większej wagi).
Dyskusja
Widzieliście gdzieś wagi w definicji problemu „cykl Hamiltona”? Nie ma żadnych, więc suma ma być równa 0 czy tam 1. Natomiast na krawędziach wpisujemy 0 jeśli w G była w danym miejscu krawędź i cokolwiek większego od 0, jeśli nie było. I graf z obrazu f(G) jest pełny.