Джумадильдаев А.С. Элементы дискретной математики (часть 1)

2332 123456 12

↓

332 23456 34

↓

32235635

↓

2 23623

↓

∅ 26 26











⇒



@



@

@rr

r

rr

G =(V, E,f).

f : E → R

+

e ∈ E f(e)

x = v

1

e

1

v

2

e

2

...v

k

e

k

v

k+1

|x| = f(e

1

)+···+ f (e

k

).

v

1

v

k

.

s V

(s)

1

V

(s)

2

v λ

(s)

(v).

V

(s)

1

⊂ V

(s+1)

1

= V

(s)

1

∪{v

i

s

},V

(s+1)

2

= V

(s)

2

\{v

i

s

}⊂V

(s)

2

,s=1, 2,...,

v ∈ V

(s)

1

(λ

(s



)

(v)=λ

(s)

(v), s



>s.

v

i

s

∈ V

(s)

1

λ(v

i

s

)=λ

(s)

(v

i

s

).

v ∈ V

(s)

1

s.

v ∈ V

(s)

1

v ∈ V

(s)

2

v ∈ V

(s)

1

u

v.

V

(1)

1

= {v

1

},V

2

= V \ V

1

= {v

2

,...,v

k

},

v

1

= v

1

(0, 0),

v

i

= v

i

(∞, 0},i=1.

s

V

(s−1)

1

= {v

1

= v

i

1

,v

i

2

,...,v

i

s−1

},V

(s)

1

= V

(s−1)

1

∪{v

i

s

},

V

2

= V \ V

1

,

v

i

s

v ∈ V x(v)

v

j

v

i

s

(λ

(s)

(v

j

),x(v

j

)).

λ

(s+1)

(v

j

) (λ

(s)

(v

i

s

)+f(v

i

s

,v

j

)

x(v

j

) v

i

s

, λ

(s)

(v

j

) >λ

(s)

(v

i

s

)+f(v

i

s

,v

j

) (λ

(s)

(v

j

),x(v

j

))

v

i

s

. v

i

s+1

,

λ

(s+1)

(v

j

)

V

(s+1)

1

= V

(s)

1

∪{v

i

s+1

},V

(s+1)

2

= V

(s)

2

\{v

s+1

}.

s = n, n = |V | G.

V

1

= V

(n)

1

.

a h



@



@



a

b

c

d

e

f

g

h

u

(1)

:= a (0, 0).

(∞, 0).



@



@



a(0, 0)

b(∞, 0)

c(∞, 0)

d(∞, 0)

e(∞, 0)

f(∞, 0)

g(∞, 0)

h(∞, 0)

V

(1)

1

= {a},V

(1)

2

= {b, c, d, e, f, g, h},

λ(a)=λ

(1)

(a)=0,

λ

(1)

(b)=∞,λ

(1)

(c)=∞,λ

(1)

(d)=∞,

λ

(1)

(e)=∞,λ

(1)

(f)=∞,λ

(1)

(g)=∞,λ

(1)

(h)=∞.

b c u

(1)

= a (4,a)

(3,a) u

(1)



@



@



a(0, 0)

b(4,a)

c(3,a)

d(∞, 0)

e(∞, 0)

f(∞, 0)

g(∞, 0)

h(∞, 0)

c u

(2)

c

u

(1)

b u

(1)

.



@



@



a(0, 0)

b(4,a)

c

(3,a)

d(6,c)

e(9,c)

f(∞, 0)

g(∞, 0)

h(∞, 0)

V

(2)

1

= {a, c},V

(2)

2

= {b, d, e, f, g, h},

λ(a)=0,λ(c)=λ

(1)

(c)=3,

λ

(2)

(b)=4,λ

(2)

(d)=6,

λ

(2)

(e)=9,λ

(2)

(f)=∞,λ

(2)

(g)=∞,λ

(2)

(h)=∞.

b, d e V

(2)

2

u

(2)

= c.

u

(2)

. d e (6,c) (9,c),

6 < ∞ 9 < ∞. b λ

(2)

(b)=4<

3+2=λ(c)+f(u

(2)

,b).



@



@



a(0, 0)

b

(4,a)

c

(3,a)

d(6,c)

e(9,c)

f(∞, 0)

g(∞, 0)

h(∞, 0)

b u

(3)

, d e

b



@



@



a(0, 0)

b

(4,a)

c

(3,a)

d

(6,c)

e(7,d)

f(11,d)

g(∞, 0)

h(∞, 0)

V

(3)

1

= {a, c, b},V

(3)

2

= {d, e, f, g, h},

λ(a)=0,λ(c)=3,λ(b)=λ

(1)

(b)=4,

λ

(3)

(d)=6,λ

(3)

(e)=9,λ

(3)

(f)=∞,λ

(3)

(g)=∞,λ

(3)

(h)=∞.

u

(3)

= b d

u

(3)

.



@



@



a(0, 0)

b

(4,a)

c

(3,a)

d

(6,c)

e

(7,d)

f(11,d)

g(∞, 0)

h(∞, 0)

d λ

(3)

(d)=6< 4+5=λ(b)+

f(u

(3)

,d). d u

(4)

.

V

(4)

1

= {a, c, b, d},V

(4)

2

= {e, f, g, h},

λ(a)=0,λ(c)=3,λ(b)=4,λ(d)=λ

(3)

(d)=6,

λ

(4)

(e)=9,λ

(4)

(f)=∞,λ

(4)

(g)=∞,λ

(4)

(h)=∞.

e f u

(4)

= d V

2

.

u

(4)

(7,d) (11,d).



@



@



a(0, 0)

b

(4,a)

c

(3,a)

d

(6,c)

e

(7,d)

f(11,d)

g(∞,e)

h(∞, 0)

u

(5)

= e

V

(5)

1

= {a, c, b, d, e},V

(4)

2

= {f,g,h},

λ(a)=0,λ(c)=3,λ(b)=4,λ(d)=6,λ(e)=λ

(4)

(e)=7,

λ

(5)

(f)=∞,λ

(5)

(g)=∞,λ

(5)

(h)=∞.

V

2

, u

(5)

= e.

g. g (12,e).



@



@



a(0, 0)

b

(4,a)

c

(3,a)

d

(6,c)

e

(7,d)

f

(11,d)

g(12,e)

h(∞, 0)

u

(6)

= f

V

(6)

1

= {a, c, b, d, e, f},V

(6)

2

= {g, h},

λ(a)=0,λ(c)=3,λ(b)=4,λ(d)=6,λ(e)=7,λ(f)=λ

(5)

(f)=11,

λ

(6)

(g)=12,λ

(6)

(h)=∞.

g h V

2

u

(6)

= f.

u

(6)

g(12,e) h(18,f).



@



@



a(0, 0)

b

(4,a)

c

(3,a)

d

(6,c)

e

(7,d)

f

(11,d)

g(12,e)

h(18,f)

g h u

(7)

g.



@



@



a(0, 0)

b

(4,a)

c

(3,a)

d

(6,c)

e

(7,d)

f

(11,d)

g

(12,e)

h(16,g)

u

(7)

= g

V

(7)

1

= {a, c, b, d, e, f, g},V

(7)

2

= {h},

λ(a)=0,λ(c)=3,λ(b)=4,λ(d)=6,λ(e)=7,λ(f)=11,λ(g)=λ

(6)

(g)=12,

λ

(6)

(h)=∞.

V

2

, h, u

(7)

= g.

h(16,g).



@



@



a(0, 0)

b

(4,a)

c

(3,a)

d

(6,c)

e

(7,d)

f

(11,d)

g

(12,e)

h

(16,g)

a h acdegh

∅

∅.

r rrr



r

@

r rr



@

rr

∅

{ ∅}

∅

{ ∅}

• (x, y, z) x, y z

•

(0, 4, 4)

• (1, 1, 6), (1, 2, 5), (2, 1, 5), (1, 3, 4), (1, 4, 3), (2, 2, 4),

(2, 3, ), (2, 4, 2)

(x, y, z), x, y z

x + y + z =8 0 ≤ x ≤ 3, 0 ≤ y ≤ 5, 0 ≤ z ≤ 8,

{{0, 0, 8}, {0, 1, 7}, {0, 2, 6}, {0, 3, 5}, {0, 4, 4}, {0, 5, 3}, {1, 0, 7}, {1, 1, 6},

{1, 2, 5}, {1, 3, 4}, {1, 4, 3}, {1, 5, 2}, {2, 0, 6}, {2, 1, 5}, {2, 2, 4}, {2, 3, 3},

{2, 4, 2}, {2, 5, 1}, {3, 0, 5}, {3, 1, 4}, {3, 2, 3}, {3, 3, 2}, {3, 4, 1}, {3, 5, 0}}.

r

r r

r



@



r

@

r

H

r

A

G

rrr

ABC

DEF



rr

r

A

D

B

C

H

F

E

@



@

@



@

@

• V (G) E(G)

• A F

•

A F

•

G

•

A

•

G

'

&

$

%

rr

r

rr

r



@



r

P



P







L

LL



H

G =(V,E) k

|V |−k ≤|E|≤(|V |−k)(|V |−k +1)/2

L(G) G

G L(A)

A

G = r rr

r

@



@

@



H



⇒ L(G)=

r



@

@

@ r

r

G =

r

r"

"

b





C

rr

A

Z



⇒ L(G)=

r

rr

r

rr

@



b



J





C

Z

G L(G),

G

Aut L(G)

∼

=

Aut G

G

r



@

3

2

4

1

rr

r



@



rr

r



J



Q

K

4

rr

r



@



r



@

r

X



p

pp

p



Z

Z



@

%

B

p

L(K

4

)=

Aut L(G) Aut G

L(K

4

) K

4

.

G

¯

G

¯

G

G.

¯

G

∼

=

G.



H



H



J

J



r

p(p−1)/2,

p

p(p − 1)/2

p ≡ 0, 1(mod 4).

A



H

H



rr

r

rr

r

rr

A



H

H



Aut G =<e>.

•

r@

@



@

@



r

rr

r

•

• ≤ 6

•

r



@

r

•

a x

@





@

H

@



@





@



@

rrrrr

r

rr

r

rrr

r

rr

rrrrrrr

Джумадильдаев А.С. Элементы дискретной математики (часть 1)

Подождите немного. Документ загружается.