初等力学

(1)

三重大学教育学部研究紀要第^{5 9} 巻自然科学 (^{2 0 0 8}) ¹ ‑ ^{2 3} 貞

初等力学グ ^ラ ^{フの} 構造

蟹江幸博^*

Str u ctur e s or E le ‑ e nta rア D y^{n a} ^m ic al G r ap h^s

Y uk i h ir o K A N I E

C o nte n ts

§¹^･ ^B^rier R e view sof F inite D ァⁿ^{a m} ic al G r ap h^s

§¹ ^‥1 C y^cle s a nd in v e rti b le D G

§1 ‥2 D eg^{r e e s}^{a n}d S iz e a nd Pe riod C ha r a cte risitc

§¹ ‥3 A tta ch ing

§¹･･4 p^‑^{m a r}y Ps e udo^‑tr e e

§2. Re al i21 atio n of D y^{n a}^m ic al G r ap h^s

§2 ‥1 S h ifts a nf Exte n sio n

§2 ‥2 E le m e nta rァ D G

§3･ Fa cts fr om E lem e nta ry N ^u^m be r T he o ry

§3 ‥1 T he G r o up ^of Redu c ed R e si du e C la s s e s

§3 ‥2 (〕^u^a^d^{r a}tic Re si du e s

§⁴. A d d itio n G r ap h A言

§5^･ M ulti pli^{c a}tio n Gr ap h Mf

§5 ‑1 Ca s e ofk ^‑ _p: p^rim e

§5 ‥2 Ca s e ofk ^‑2^m(^m ^, ⁰)

§5･･3 Ca s e of k ⁼ p

2(p^: ^od d p^rim e)

§5･･4 Ca s e ofk ⁼ _p^m(m , 0_,p⁼p^rim e)

§5･･5 Ca s e of Com p^{o s}ite Num be r sk

§5 ‥6 M is c el la r l e O u S Ca s e s

2 3 4 4 5

5 6 6

6 6 8

8

9 1 3 1 5 1 7 1 8 2 1 2 3

Intr o d u ctio n

I p^{r o}p^{o s e}d the c o n c ep^t ^of d_ァn a m ic al _gr aphsfらr C linic al M athe m atic s E du c atio n in [²]^, ^{a n}^{d d i}s c u s s ed

their m athe m atic althe o ry iⁿ ^the c a s e ofr edu c ed divis o r s u m sin[³]^, ^{a n}^d ⁱⁿ ^t^h^e ^{c a s e} ^o^fr e v e r s ed diffe r e n c e s

in [⁵]^･ Â ⁿ^{d i}ⁿ [⁸]^, Î^d ê^t^{e r m}ⁱⁿ ê^d ^t^hê ^{n u} ^m ^b^{e r} ô^r^t^hê ⁱ^{s o} ^m ^{o r}p his m cla s s e s of d_yn a mic al g^{r a}p h^s ^with v e rte x n u m be rk ≦10･ T he r e w e kn o w the str u ctu r e s of d _y_m a mic al g^{r a}p h^s ^{a r e} ^{r a}^the r c o m p li^{c a}^têd e v e n in s u ch

a s m all siz e c a s e.

In th is n ote, w e will d e s c ribe s o m e str u ctu r e s or ba sic ele m e nta rァ d_ァn a mic al _gr aph s_, e sp^{e c}iall y ^or

ad d itio n g^{r a}phs a nd m ulti_{p li}c atio n g^{r a}phs･ W e u s e s o m tim e sthe ab b r e viatio n D G fo r d yⁿ ^a ^mic al g^{r a}phs･

*

･M ath･D ep^t^･ ^of Fa c･ of E d ･,M ie U nive r s lty

(2)

§¹ ^･ ^B ^rⁱê^{f R} ^{e v}ⁱê ^w ^s ô^{f F i}ⁿ^{i t}ê D y ^{n a} ^m ic al G r ap h ^s

L et V b e a finite s et^･ A d_yn a mic al _graph a ^‑(^V ^,Ê)ⁱ^s âⁿ ô^rⁱêⁿ^têd g^râph on V w ho s e every ^vê^rtex v ∈V ha s o nl_y one o ut gôing êd_ge from v

, thatis

, th ere is o nl_y one vetex w with (^v^, ^w) ^∈ Ê ^･ Â ⁿ ô^rⁱêⁿ^tê^d ê^d^gê

(^v^, ^w) ^∈Ê ⁱ^s ^{s o} ^m ê^tⁱ^{m e s} ^d^râ^w ⁿ ^{a s} ^′û ^‑ ^w âⁿ^d ⁱ^s ^{c a}^llê^d ^{a n} â^{r r}ô ^w ^.

Denote b_y D(^V) ^t^hê ^sê^t ô^f â^{ll d} ^y^{n a}^mⁱ^{c a}^l g^râphs on V , which is bij^{e c}^tⁱ^vê ^tô ^t^hê ^{s e}^t ^M â^p(^V^,^V) ô^f^t^h ê

m ap^s ôf V toi ts elf･ T he c or re spôⁿdenc eis g^{l V}êⁿ ^{a S} follows^.

G ive n f ∈ M ap(^V^,^V)^, ^tâ^kê ^t^hê ^g^râ^p^{h E}(I) ^‑((^v^,f(^v)) I ^v ^∈ ^V) ô^f ^t^hê ^{m a}pf ^{a s}^t^h^{e s e}^t ô^f ê^d^g^{e s} ô^{f G}^,

then G(^f) ^‑ (^V^, Ê(Î))ⁱ^s â ^d^yⁿ â^mⁱ^{c a}l g^{r a}ph ^.

C on vers el_y_, gi^vêⁿ â ^d yⁿ ^{a m}ic al _graph a ^‑ (^V^,Ê) ôⁿ ^V ^, ^f^{o r} âⁿy ^v E V w e have onl_y o n e vertex w E V

with(^v^,^w) ^∈ Ê ^･ ^Sô ^lê^t Î(^v) ^‑ ^w ^･ ^D êⁿô^{t i}ⁿg f ^byf(â)^, ^w ê gêt that G ^‑ a(f(^G)) ^{a n}^d f ^‑ f(^G(Î))^･

T w o m ap^s f ∈ M ap(^V ^,^V) âⁿ^d a ∈ M ap(^W ^, ^W) â^rê ^{c a}^llê^{d i}^{s o m o r}phic, ifth ere exists a bij^{e c}^tⁱ^{o n} p ^: V ^‑ W (^{c a}^llê^d âⁿ ⁱ^{s o m o r}^p^hⁱ^{s m}) ^{s a}^tⁱ^s^f^yⁱⁿ^{g t}^hê ê^q^{u a}^lit y

p ^o f ^‑ 9 ⁰ P ^⇔f ^‑ p‑¹ o g ^o p ^.

T h en w e w ri te a s f 空 g^, âⁿd c all_thed _yna mical _gr aphs a(I) âⁿ^{d G}(g) â^rêⁱ^{s o m} ^{o r}phic wi th e a ch other and den oted b_y G(^f) ^空 ^G(^g)^･

In de s cribin _{t ,}^o

'

stru ctu r e s explicitel_y_, _there are s o m e c a s e s whe r eitisim p^o^rta nt to sp^{e c}if_ylab els of verte c e s, a nd to dist ing^uish is o m orph ic D G^'s^. S o w e de n ote p ^*f ^‑_.p ^｡f ^｡ p

1 a nd _p * G(I) ^‑ ^a(p ^*f)^, ^aⁿ^d ^{c a}^ll

ア^* G(^f) ^t^hê ^ダ^ー^t^{r a n}^S^fê^r ô^f ^t^hê ^{D G a}(f )^･ ^{T h}êⁿ ^wê ^{s a}y t^･hat the D G G(f) ôⁿ ^V ⁱ^s p ^‑tra n sfered t^･o the D G

･ア^* G(^f) ôⁿ ¹⁴^'^･ ^M ô^r^{e o}^vê^r^, ⁱ^{f G}^′ⁱ^s â ^{D S G} ô^{f G} ^,^t^･^hêⁿ p ^* G^′is als o a D S G of _p * G(^{I )}^.

If f is bij^{e c}^ti^vê^, ^t^h ê ^d y^{n a m}ic al _graph G(f ¹) ^dê^fⁱⁿê^{d b}y thein vers e m ap p iⁿg r ^l ⁱ^s ^{c a}^llê^d ^t^,^hê ⁱⁿ^v^{e r s e}

g^râph of G ^‑ G(^f)^, âⁿ^d ^G ⁱ^s ^{c a}^llê^d ⁱ^{n v}^{e r}^ti^blê^. ^W ^rⁱ^tê ^G ¹ ^‑ ^G(f ¹)^fô^r ^t^hê ⁱⁿ^vê^r^{s e} ô^{f G} ^, ^t^h^{e n} ^{i t} ^{c a}ⁿ ^bê

obtained b_y reversl ng ^all di^re cti^･o n s of ar row s of C

D e n ote h y 7)｢ V lt･he s et･ ô^f â^{l一 d}^v ⁿâ^･^{n l}^j^{c a}^l g^{r f l}^,Phs o n V _, a nd hv 7)^′｢Vl the s et of allin v e rtihle dv n a･mic alr

＼ / ^tノ＼ ′

g^râphs on V I T h e c a^rdinal_{i t y} of V is c alled of siz e of G ^‑ (^V^, Ê)^, ^dêⁿô^tê^{d b}y ^s ^‑ ^s(^G)^, ^w ^hⁱ^c^h ^{c o}ⁱⁿ^cⁱ^d^{e s}

with _the nu m ber # Ê ô^f ê^d_g^{e s} ô^{f a} ^.

D en ote b_y か(^v) ^a^,ⁿ^d ^D

′

(^v) ^t^hê ^{s e}^t ô^{f i}^{s o m o r}ph is m cla s s e s of 了)(^V) âⁿ^{d D} ^′(^V) ^{r e s}^p^{e c}^tⁱ^vê^ly^. Now w e p^rêp^{a r e} ^{s o m e} ba sic n otio n s abo ut D G .

L et G ^‑(^V ^.Ê) ^‑ ^G(I) ^bê â ^{D G} ^･ ^{A d}y^{n a m} ic al_graph G ^' ^‑ (^V ^'^,Ê)^' ⁱ^{s c a}^llê^d ^dy^{n a m}ic als ub_graph(^{D S G})

of G, if V ^' c v , E ^' c E and every ^ed_gein E ^' c onsists of verte c e s in V^'.

For a vertex ^,u ∈ V , the s et of all^'d e s c e nda nts^' of v:

V ⁺(ⁱ)^, ^‑ †^w ^∈ ^V F ^w ^‑ fâ(^v)^fô^r ^{s o} ^m ê â ^>_̲ ⁰)

is a D S G b_y.û âl ld is c all^, ed thefû^t^{u r e} ô^f ^v^. ^{T h}ⁱ^{s s u}^bg^râph is the minim al s ub_gr aph c o ntaining the ve rtex v_, s oi t is als o c alled the s ub g^râph _gen erated b_yru a nd is denoted b_y(^v)^. ^Fô^r âⁿy ^{s u}bs et U ⊂ V, den ote b_y

(Û) ^t^hê ^{D G} gêⁿ ê^râted b_y U .

For a vertex u ∈ V ,the s et of all ^‑anc e sterts^' of 1) :

V‑(û⁾ ^‑ ( ^w ^∈ ^V 卜^L⁷ ^‑ ^fâ(^w)^fô^r^{s o m e} â ≧⁰)

is called th e p^a^st of u. butit is llOt a D S G in g^{e n e}^r^al.

Fo r an integê^r ⁿ^,≧⁰^･^d êⁿô^tê^by G⁽^",) the sub_graph G(flf^れ(^V)) ^‑ (fⁿ(^V)) ^{o n} ^t^･^h êÎ^‑ⁱⁿ^v^{a r}ⁱâⁿ^t ^sû^b^{s e}^t^fⁿ(^V)^,

a nd c all it the n‑^t^hfû^tû^{r e} g^{r a}ph. A ls o den ote G ⁽¹⁾ ^‑ G ^',and c alli t the de riv ed _gr aph ôf G ^. T he n w e gê^t

v ^‑ f^O(^v)∋^f^l⁽^v⁾⊇^･ ^･^･∋^f^h⁽^v⁾ ^‑ ^f^{h + 1}⁽^v⁾ ^‑

‑ ² ‑

初 等 力 学

初等力学