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

گراف ساده $(G = (V,E $به همراه تابع $\sigma:E(G)\to \{+.-\}$ را يك گراف علامت دار گويند و آن را با $G^\sigma$نشان مي دهند. ماتريس مجاورت گراف علامت دار را با $A^\sigma=[a_{ij}]$نشان مي دهند كه در آن اگر$e=ij$ يال و $\sigma(ij)=+ $انگاه $a_{ij}=+1$ و اگر $e=ij$ و $\sigma(ij)-$ آنگاه $a_{ij}=-1$ در غيراين صورت صفر تعريف مي شود.در اين مقاله،گراف هاي دوبخشي $G$ و تابع $\sigma$ طوري تعيين مي شوند كه ماتريس مجاورت $G^\sigma$ دقيقا دو مقدار ويژه متمايز داشته باشد.