گراف های دوبخشی علامت دار با دو مقدار ویژه متمایز

Abstract

گراف ساده G=(V,E) به همراه تابع f روی E(G) را یک گراف علامتدار گویند و آن را با G^f نشان می دهند. ماتریس مجاورت گراف علامت دار را با A^f=[a_ij] نشان می دهند که در آن اگر e=ij یال و f(e)=+ آنگاه a_ij=1 , اگر e=ij یال و f(e)=- آنگاه a_ij=-1 و گرنه صفر تعریف می شود. در این مقاله گراف دوبخشی G و تابع f چنان تعیین می شوند که G^f دقیقا دو مقدار ویژه متمایز داشته باشد.