Beberapa Syarat Graf Tidak Bersahabat

Abstract

Misalkan G sebuah graf dengan himpunan titik G dilambangkan dengan V(G). Misalkan v sebuah titik di G. Persekitaran titik v di G, dilambangkan dengan N(v), adalah himpunan semua titik G yang berhubungan langsung dititik v. Misalkan S⊆V(G). Sebuah titik v∈S dikatakan tidak bersahabat jika banyak titik persekitaran v di V(G)\S lebih dari atau sama dengan banyak titik perekitaran v di S. Dengan kata lain, |N(v)∩V(G)\S|≥|N(v)∩S|. Sedangkan titik v dikatakan sangat tidak bersahabat apabila banyak titik persekitaran v di V(G)\S lebih besar dari banyaknya titik persekitaran v di S. Dengan kata lain, |N(v)∩V(G)\S|>|N(v)∩S|. Jika setiap titik v∈S dan setiap titik u∈V(G)\S adalah titik-titik yang tidak bersahabat maka (S,V(G)\S) dinamakan sebuah bipartisi tidak bersahabat dari graf G, dan G dikatakan graf tidak bersahabat. Begitu juga untuk setiap titik v∈S dan setiap titik u∈V(G)\S) dinamakan sebuah bipartisi sangat tidak bersahabat dari graf G, dan G dikatakan graf sangat tidak bersahabat.