Элементы теории графов

  • View
    88

  • Download
    1

Embed Size (px)

DESCRIPTION

. { - - - , , - - - , , - - }. - PowerPoint PPT Presentation

Transcript

  • { - - - , , - - - , , - - }

  • 1736 . 1 2 3 4 5 6 7 C C , A , D , B ADBPregel

  • . : , , . abcdgfe , . , .

  • (), : G = { V, E } , V , E - V V , , , , . , . . . 1936 . G = { V, E } , ().

  • , , (). , , . . , , , . . . , , , , , . . . V , E ().

  • e = ( v1, v2 ) , e E , e (v1, v2 ) , v1 =v2, e . v1 ,v2 , . - , . v d (v) , , . do (v) di (v) . , , . ( , , ).

  • , , . (), ( ), (, , ). .123452, 3, 5, 4 2, 3, 4, 5, 1, 4, 3 , 3, 1, 4, 5,1, 2 , 2, 3,1,4, 5,1, 2 , 2, 3, 4, 5,1, 2 2, 3,1,4, 3,1, 2 ,

  • . 2, . . x1, x2, .., xn . xn xn-1, , c , y . y , x1, x2, ..,xn, y . y : y = xi , i < n-1 . x1, x2, .., xn .333322

  • , 3 ?

  • , , . , , . , , . Kn . n , - . (m) :

  • , , V(a) . . , .

  • ( ). . G xi i, : x1 + 2x2 ++ kxk = 2|E| , , . , x2i+1 . 0 . d, d . , .2e(G) = 2*4 = 8

  • G (V, E ) , n . Aij ( Aij : 1 - , 0 - )

  • , G (V, E ) . () 1 n , () 1 m . , i j , . , . , . : 1, i j , -1, , 0, .

  • , , () . , , , , , , , , ..

    ****************