- ±×·¡ÇÁÀÇ °³³ä
- ±×·¡ÇÁ G´Â Çϳª ÀÌ»óÀÇ "Á¤Á¡(³ëµå)µéÀÇ ÁýÇÕ V"
¿Í "µÎ Á¤Á¡ÀÇ ½ÖÀ¸·Î ±¸¼ºµÇ´Â °£¼±(¸µÅ©)µéÀÇ
ÁýÇÕ E" ·Î ÀÌ·ç¾îÁö¸ç, G=(V,
E) ·Î Ç¥ÇöÇÑ´Ù. ¶ÇÇÑ, V(G)´Â ±×·¡ÇÁ G¸¦ ±¸¼ºÇÏ´Â Á¤Á¡µéÀÇ
ÁýÇÕÀÌ°í, E(G)´Â °£¼±µéÀÇ ÁýÇÕÀÌ´Ù.
- °£¼±À¸·Î ¿¬°áµÈ
µÎ Á¤Á¡Àº ÀÎÁ¢(adjacent)ÇÑ´Ù.
- °£¼±Àº °¡ÁßÄ¡(weight)
¶Ç´Â ºñ¿ë(cost)À» °¡Áú
¼ö ÀÖ´Ù.
- ÁÖ¿ä
°³³ä
- ÀÎÁ¢(adjacent) : (V1,V2)°¡ E(G)¿¡ ÀÖ´Â °£¼±À̸é, V1 °ú
V2´Â ÀÎÁ¢
- °æ·Î(Path) : µÎ Á¤Á¡ »çÀÌ °£¼±À¸·Î ¿¬°áµÈ ÀÏ·ÃÀÇ Á¤Á¡
- ·çÇÁ(loop) : (V,V)ó·³ ÀÚ±â ÀÚ½ÅÀ¸·Î µÇµ¹¾Æ¿À´Â °£¼±
- »çÀÌŬ(cycle) : °æ·ÎÀÇ ½ÃÀÛÁ¡°ú ³¡Á¡ÀÌ °°Àº °æ¿ì
- ÁøÀÔÂ÷¼ö(in-degree) : ÀÓÀÇ ³ëµå¿¡ µé¾î¿À´Â °£¼±ÀÇ ¼ö
- ÁøÃâÂ÷¼ö(out-degree) : ÀÓÀÇ ³ëµå¿¡¼ ³ª°¡´Â °£¼±ÀÇ ¼ö
- Â÷¼ö(degree) : ÁøÀÔÂ÷¼ö + ÁøÃâÂ÷¼ö
- ´Ü¼ø °æ·Î : °æ·Î»óÀÇ ¸ðµç Á¤Á¡ÀÌ ´Ù¸¥ °æ¿ì
- ´Ü¼ø ¼øȸ : ¸ðµç °£¼±ÀÌ ´Ù¸£°í ½ÃÀÛÁ¡°ú ³¡Á¡Àº °°Àº °æ·Î
|
|