UNIVERZITET U BEOGRADU
MATEMATIQKI FAKULTET
Zoran S. Pucanovi
ANALIZA PRSTENA I MODULA
PRIDRUIVANjEM GRAFOVA
DOKTORSKA DISERTACIJA
BEOGRAD, 2012.
UNIVERSITY OF BELGRADE
FACULTY OF MATHEMATICS
Zoran S. Pucanovic´
THE ANALYSIS OF THE RINGS AND
MODULES USING ASSOCIATED
GRAPHS
DOCTORAL DISSERTATION
BELGRADE, 2012.
MENTOR:
dr Zoran Petrovi,
vanredni profesor, Univerzitet u Beogradu, Matematiqki fakultet
QLANOVI KOMISIJE:
dr Aleksandar Lipkovski,
redovni profesor, Univerzitet u Beogradu, Matematiqki fakultet
dr Gojko Kalaj
i,
vanredni profesor, Univerzitet u Beogradu, Matematiqki fakultet
dr Ljubomir Quki,
vanredni profesor, Univerzitet u Beogradu, Graevinski fakultet
Datum odbrane:
Posveeno
mojoj supruzi Nataxi
ANALIZA PRSTENA I MODULA
PRIDRUIVANjEM GRAFOVA
SAETAK
Ova doktorska disertacija prouqava razliqite osobine komutativnih
prstena i modula algebarsko kombinatornim metodama. Ako se graf na
odgovarajui naqin pridrui prstenu R ili R-modulu M , onda ispiti-
vanjem njegovih osobina dolazimo do korisnih informacija o R i M .
U ovoj tezi odreen je radijus totalnog grafa komutativnog prstena
R u sluqaju kada je taj graf povezan. Tipiqna raxirenja kao xto su
prsten polinoma, prsten formalnih redova, idealizacija R-modula M
i prsten matricaMn(R) takoe su ispitani. Ustanovljene su veze izmeu
totalnog grafa polaznog prstena R i totalnih grafova ovih raxirenja.
Definisanjem totalnog grafa modula dato je jedno uopxtenje totalnog
grafa komutativnog prstena. Ispitane su i dokazane njegove razliqite
osobine. Ustanovljene su veze sa totalnim grafom prstena kao i neke
veze sa grafom delitelja nule.
U cilju boljeg razumevanja qistih prstena, uveden je qisti graf CΓ(R)
komutativnog prstena sa jedinicom R. Detaljno su ispitane njegove
osobine. Daljim istraivanjem qistih grafova dobijeni su dodatni
rezultati vezani za druge klase komutativnih prstena.
Jedan od predmeta ove teze je i istraivanje osobina odgovarajueg
linijskog grafa L(TΓ(R)) totalnog grafa TΓ(R). Data je kompletna
klasifikacija svih komutativnih prstena qiji su linijski grafovi to-
talnog grafa planarni ili toroidalni. Dokazano je da za ceo broj
g ≥ 0 postoji samo konaqno mnogo komutativnih prstena takvih da je
γ(L(TΓ(R))) = g.
U ovoj tezi su takoe klasifikovani svi toroidalni grafovi koji
su grafovi preseka ideala komutativnog prstena R. Dato je i jedno
poboljxanje postojeih rezultata o planarnosti ovih grafova.
Kljuqne reqi: komutativni prsteni, qisti prsteni, moduli, delitelji
nule, totalan graf, qisti graf, linijski graf, graf preseka, rod grafa
Nauqna oblast: Matematika
Ua nauqna oblast: Algebra
UDK broj: [512.55:512.71]:519.171(043.3)
AMS klasifikacija: 13A99, 13C99, 13H99, 05C10, 05C25
THE ANALYSIS OF THE RINGS AND MODULES
USING ASSOCIATED GRAPHS
ABSTRACT
This dissertation examines various properties of commutative rings and modules
using algebraic combinatorial methods. If the graph is properly associated to a ring
R or to an R-module M , then examination of its properties gives useful information
about the ring R or R-module M .
This thesis discusses the determination of the radius of the total graph of a
commutative ring R in the case when this graph is connected. Typical extensions
such as polynomial rings, formal power series, idealization of the R-module M and
relations between the total graph of the ring R and its extensions are also dealt
with.
The total graph of a module, a generalization of the total graph of a ring is
presented. Various properties are proved and some relations to the total graph of a
ring as well as to the zero-divisor graph are established.
To gain a better understanding of clean rings and their relatives, the clean graph
CΓ(R) of a commutative ring with identity is introduced and its various proper-
ties established. Further investigation of clean graphs leads to additional results
concerning other classes of commutative rings.
One of the topics of this thesis is the investigation of the properties of the cor-
responding line graph L(TΓ(R)) of the total graph TΓ(R). The classification of
all commutative rings whose line graphs of the total graph are planar or toroidal
is given. It is shown that for every integer g ≥ 0 there are only finitely many
commutative rings such that γ(L(TΓ(R))) = g.
Also, in this thesis all toroidal graphs which are intersection graphs of ideals
of a commutative ring R are classified. An improvement over the previous results
concerning the planarity of these graphs is presented.
Keywords: commutative rings, clean rings, modules, zero-divisors, total graph,
clean graph, line graph, intersection graph, genus of a graph
Scientific area: Mathematics
Scientific field: Algebra
UDC number: [512.55:512.71]:519.171(043.3)
AMS Subject Classification: 13A99, 13C99, 13H99, 05C10, 05C25
Sadraj
1 Uvod 1
1.1 Osnovni pojmovi i terminologija . . . . . . . . . . . . . . 1
1.1.1 Pojmovi iz teorije komutativnih prstena . . . . . . 1
1.1.2 Pojmovi iz teorije grafova . . . . . . . . . . . . . . 3
2 Totalni graf komutativnog prstena 7
2.1 Definicija totalnog grafa . . . . . . . . . . . . . . . . . . 7
2.2 Radijus totalnog grafa . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Z(R) je ideal u R . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Z(R) nije ideal u R . . . . . . . . . . . . . . . . . . . 10
2.3 Totalni graf nekih raxirenja prstena . . . . . . . . . . . . 12
2.3.1 Prsten polinoma . . . . . . . . . . . . . . . . . . . . . 12
2.3.2 Prsten formalnih redova . . . . . . . . . . . . . . . 14
2.3.3 Idealizacija . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.4 Matrice . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Totalni graf modula 21
3.1 T (M) je podmodul modula M . . . . . . . . . . . . . . . . . . 21
3.2 T (M) nije podmodul modula M . . . . . . . . . . . . . . . . . 25
4 Qisti graf 30
4.1 O strukturi grafa CΓ(R) . . . . . . . . . . . . . . . . . . . . 32
4.2 Povezanost i dijametar grafa CΓ(R) . . . . . . . . . . . . . 34
4.3 Rod qistog grafa . . . . . . . . . . . . . . . . . . . . . . . . . 42
5 Linijski graf totalnog grafa 49
5.1 Struktura i osobine grafa L(TΓ(R)) . . . . . . . . . . . . . 50
5.2 Utapanja L(TΓ(R)) . . . . . . . . . . . . . . . . . . . . . . . . 53
6 Graf preseka ideala 62
6.1 O planarnosti grafa G(R) . . . . . . . . . . . . . . . . . . . 63
6.2 Toroidalnost grafa G(R) . . . . . . . . . . . . . . . . . . . 65
7 Zakljuqak 74
Literatura 79
Biografija 85
PREDGOVOR
Egzistencija pravih delitelja nule obiqno prouzrokuje probleme u
radu sa komutativnim prstenima. Mada imaju multiplikativno svo-
jstvo, njihovi zbirovi ne mogu se kontrolisati i zatvorenost sabiranja
u opxtem sluqaju nije ispunjena. Tako, jedan veoma vaan podskup u
prstenu nema algebarsku strukturu, ne mora biti ni potprsten, a ni
ideal. Njegov podskup nilpotentnih elemenata je ideal, pa se nepravil-
nosti u prstenima izazvane nilpotentima mogu izbei posmatranjem
odgovarajuih redukovanih prstena. U komutativnoj algebri u znaqa-
jnoj meri zastupljen je rad sa domenima, komutativnim prstenima bez
pravih delitelja nule. Oni su naravno mnogo pogodniji za izuqavanje,
ali problemi izazvani postojanjem pravih delitelja nule u prstenu ne
mogu se uvek izbei. Na primer, sama definicija jednoznaqne faktor-
izacije, jedne od fundamentalnih osobina komutativnih prstena, po-
drazumeva da on nema pravih delitelja nule. Postoje naravno mnoga uop-
xtenja i manje ili vixe uspexni pokuxaji da se pojam jednoznaqne fak-
torizacije proxiri i na komutativne prstene koji nisu domeni. Mnogi
znameniti algebristi (poput Andersona, Gilmera, Kaplanskog, Nagate
i drugih) prouqavali su sa raznih aspekata ponaxanje delitelja nule u
komutativnim prstenima i problematiku u vezi sa njima.
Dublja analiza delitelja nule u komutativnim prstenima, naroqito u
Neterinim, data je u [32]. Od vanijih rezultata o strukturi delitelja
nule istaknimo poznati rezultat iz ove knjige ([32, teorema 2]): Skup
delitelja nule komutativnog prstena je unija prostih ideala. Dosta
rezultata o ovoj problematici moe se nai u monografiji [29]. Znaqa-
jan doprinos ovoj temi dao je i N.Ganesan dokazavxi da je prsten sa
konaqno mnogo delitelja nule konaqan ([24, teorema 1]). Osobine i uti-
caj delitelja nule na osobine prstena i dalje su, kao i u proxlom veku,
atraktivan problem za mnoge matematiqare.
Poslednjih desetak godina doxlo je do promene pristupa u prouqa-
vanju strukture delitelja nule u prstenima. Sa qisto algebarskog pris-
tupa prelazi se na algebarsko kombinatorne metode i povezuju se dve
razliqite discipline: komutativna algebra i teorija grafova. Pio-
nirski rad u povezivanju prstena i grafova pripada Beku [13] i nas-
tao je 1988. godine. Ipak, pravi zamah u ovoj oblasti poqinje od
1999. godine radom [8] Andersona i Livingstona. Autori komutativnom
prstenu R pridruuju graf delitelja nule Γ(R), tako xto za temena
grafa uzimaju sve prave delitelje nule u R. Temena x i y susedna su
u Γ(R) akko je xy = 0. Oni izmeu ostalog dokazuju da je (neoqeki-
vano) Γ(R) uvek povezan, i vixe, diam(Γ(R)) ≤ 3 [8, teorema 2.3]. Ve-
liko iznenaenje predstavlja qinjenica da delitelji nule imaju vrlo
specifiqnu grafovsku strukturu iako nemaju jasnu algebarsku. Stoga
ovaj rad privlaqi veliku panju i mnogi autori nastavljaju da slede
ovaj pristup u prouqavanju delitelja nule u komutativnim prstenima.
Svakako, ve na osnovu pomenute teoreme vidimo da ima algebarske ko-
risti od uvoenja ovog grafa. Postavljaju se zato i druga zanimljiva
pitanja u vezi sa Γ(R). Na primer: Kada je on kompletan ? U kojim
sluqajevima je planaran, a u kojim toroidalan ? Kakva je struktura
grafa delitelja nule prstena polinoma i prstena formalnih redova nad
R ? Za koje prstene je diam(Γ(R)) ≤ 2 ? U kakvoj su vezi ovi pojmovi
iz teorije grafova sa algebarskim svojstvima prstena R ? U radovima
[8, 9, 11, 12, 35, 45, 46] istrauju se razne osobine grafa Γ(R) i daju se
odgovori na neka od ovih pitanja. U radu [6] ovi radovi su sistemati-
zovani i dat je pregled glavnih rezultata vezanih za graf Γ(R).
Naravno, graf se moe pridruiti prstenu ili nekoj drugoj alge-
barskoj strukturi na razne naqine u zavisnosti od toga koje osobine
prouqavamo. Korist od toga moe biti manja ili vea, tj. ne moemo
uvek oqekivati povratnu informaciju o prstenu iako znamo strukturu
njemu pridruenog grafa. Qesto se dexava da neizomorfni prsteni
imaju izomorfne pridruene grafove. Takav je sluqaj i sa grafom Γ(R).
U cilju efikasnijeg rexavanja ovog i sliqnih problema, dolazi se do
raznih uopxtenja ovog grafa, a uvode se i novi grafovi. Anderson i Ba-
davi u radu [7] definixu totalni graf komutativnog prstena T (Γ(R)).
Za temena uzimaju sve elementa prstena R. Temena x i y su susedna akko
je x + y delitelj nule u R. Ovako definisan graf favorizuje aditivna
svojstva delitelja nule u odnosu na multiplikativna, kojima je data
prednost u Γ(R). Struktura grafa T (Γ(R)) prirodno zavisi od toga da
li delitelji nule formiraju ideal u R ili to nije sluqaj, tako da se
ovde pojavljuju zanimljive veze sa algebarskim osobinama prstena R. O
ovom grafu bie dosta reqi u ovoj disertaciji.
Bekova ideja pokazala se korisnom i u rexavanju razliqitih prob-
lema u teoriji komutativnih prstena koji ne moraju imati veze samo sa
deliteljima nule. U [21] autori generalixu ovu ideju radi proqavanja
faktorizacije u domenima i definixu ireducibilne divizor grafove, u
oznaci Irr(R). Koristei ove grafove oni karakterixu razne klase dom-
ena, ukljuqujui i domene sa jednoznaqnom faktorizacijom.
Kako struktura komutativnih prstena zavisi pre svega od njihovih
ideala, prirodno je definisati i grafove bazirane na idealima. U
radu [50], autori definixu komaksimalan graf uzimajui za temena sve
elemente prstena R. Temena x i y su susedna akko Rx + Ry = R. Vixe
o komaksimalnim grafovima qitalac moe nai u [37]. U radu [18] au-
tori definixu graf preseka ideala G(R), tako xto za temena uzimaju sve
netrivijalne ideale u R. Temena (ideali) I i J susedna su u G(R) akko
je I ∩ J 6= 0. U ovom radu baviemo se i nekim pitanjima vezanim za
ovaj graf. Naravno, ovo su samo neke od mogunosti za pridruivanje
grafa komutativnom prstenu. Sliqno se moe postupiti i u nekomu-
tativnim prstenima (videti, na primer [47]). Zainteresovani qitalac
moe u literaturi nai jox dosta grafova asociranih prstenima, ali
i drugim algebarskim strukturama: semigrupama, grupama, parcijalno
ureenim skupovima, itd.
U ovoj disertaciji izuqavaju se osobine prstena i modula analizom
njima pridruenih grafova. Prvobitna ideja bila je prouqavanje struk-
ture delitelja nule u komutativnim prstenima sa qisto algebarskog
stanovixta. Ve prvi povrxan pregled postojee literature i savre-
menih rezultata u ovoj oblasti doveo nas je do algebarsko – kombi-
natornog pristupa ovoj problematici. Motivaciju za razmatranje ovog
problema autor ovog rada i njegov mentor pronaxli su u gore citiranim
radovima. Vremenom su se poqetna interesovanja za grafove pridruene
prstenima sa deliteljima nule proxirila i na neke druge klase prstena,
kao i na linijske grafove i grafove preseka ideala. Njima je i posveen
vei deo ovog rada.
U uvodnoj glavi ovog rada ukratko su izloeni osnovni pojmovi i
terminologija iz teorije grafova i teorije komutativnih prstena. Tu
su takoe dati iskazi postojeih tvrenja i teorema koje kasnije u radu
koristimo. Ove teoreme navodimo bez dokaza, sa referencama gde se oni
mogu nai. Ostale glave sadre originalne rezultate.
Druga glava bazira se na radu [40] i posveena je prouqavanju to-
talnog grafa T (Γ(R)) i njegovih asociranih podgrafova, za komutativan
prsten R. Specijalno, ovde se odreuje radijus za T (Γ(R)) i razma-
traju se povezanost i dijametar za T (Γ(R[X])), T (Γ(R[[X]])), T (Γ(R(+)M))
i T (Γ(Mn(R))).
U treoj glavi koja se oslanja na rad [43], prezentovana je jedna gen-
eralizacija grafa T (Γ(R)). Za R-modul M nad komutativnim prstenom
R definixemo totalni graf modula T (Γ(M)). Ulogu delitelja nule u
T (Γ(M)) preuzimaju torzioni elementi modula M . Ispostavlja se da je
struktura ovog grafa u tesnoj vezi sa strukturom T (Γ(R)).
Centralno mesto ovog rada je qetvrta glava u kojoj su izloeni
rezultati iz rada [15]. Motivisani definicijom qistog prstena defin-
ixemo qisti graf CΓ(R). Za skup temena uzimamo sve elemente komuta-
tivnog prstena R. Temena x i y su susedna akko je x + y invertibilan
ili idempotentan. Razmatramo tipiqna pitanja kao xto su povezanost,
obim i dijametar ovog grafa i njihovu algebarsku interpretaciju u
posmatranom prstenu. Mada je uvoenje ovog grafa motivisano klasom
qistih prstena, ispostavlja se da je njegova struktura u tesnoj vezi i sa
drugim klasama prstena, kao xto su, na primer, poluperfektni komuta-
tivni prsteni. U ovoj glavi dajemo i odgovor na pitanje kada je CΓ(R)
planaran a kada toroidalan, za konaqan prsten R.
Peta glava je kombinatornog karaktera. U ovoj glavi izloeni su
glavni rezultati iz rada [41]. Za komutativan prsten R, razmatra se
linijski graf L(T (Γ(R))) totalnog grafa T (Γ(R)). Prouqavaju se neke
njegove osobine sa posebnim akcentom na pitanje utapanja ovog grafa.
Izmeu ostalog, dokazujemo da za fiksiran ceo broj g ≥ 0 postoji samo
konaqno mnogo komutativnih prstena R takvih da je L(T (Γ(R))) roda g.
Xesta glava bavi se pitanjem toroidalnosti grafa preseka ideala
G(R) i bazirana je na radu [42]. U manjoj meri obrauje se i pitanje pla-
narnosti. Glavni rezultat xeste glave je klasifikacija svih toroidal-
nih grafova koji su grafovi preseka ideala nekog komutativnog prstena.
Za nesebiqnu pomo pri izradi ove disertacije zahvaljujem se mom
mentoru Zoranu Petroviu. Zahvaljujui njegovim primedbama neki od
dokaza su znatno krai i elegantniji a glavni rezultati jasnije prezen-
tovani. Njegove ideje i sugestije, kao i strpljenje u radu sa mnom, po-
mogle su da ova disertacija ugleda svetlost dana.
Beograd,
Oktobar 2012. Zoran Pucanovi
GLAVA 1
UVOD
U ovoj glavi daemo kratak pregled osnovnih pojmova i definicija iz
teorije grafova i teorije komutativnih prstena koje u daljem radu ko-
ristimo. Upoznaemo se sa terminologijom i navexemo nekoliko poz-
natih teorema i tvrenja potrebnih za nax rad. Generalne reference za
teoriju komutativnih prstena su standardni u
benici komutativne al-
gebre [10] i [32]. Xto se tiqe teorije grafova, slediemo terminologiju
iz [22] i [52]. Ukoliko neki od pojmova nije definisan ili su potrebna
detaljnija objaxnjenja, qitalac ih moe pronai u ovim knjigama.
1.1 Osnovni pojmovi i terminologija
1.1.1 Pojmovi iz teorije komutativnih prstena
Ukoliko se ne naglasi drugaqije, prsten R u ovom radu bie uvek
komutativan prsten sa jedinicom i R∗ = R \ {0}. Element a ∈ R je
delitelj nule ako je ab = 0 za neko b ∈ R∗. Sa Z(R) oznaqavamo skup
delitelja nule prstena R i sa Z(R)∗ = Z(R)\{0} skup pravih delitelja
nule. Reg(R) je skup regularnih elemenata prstena R, Reg(R) = R\Z(R) i
Nil(R) je ideal njegovih nilpotentnih elemenata. Skupove invertibil-
nih i idempotentnih elemenata prstena R oznaqavamo redom sa U(R) i
Id(R). Za prsten polinoma, formalnih redova i idealizaciju R-modula
M koristimo standardne oznake R[X], R[[X]] i R(+)M . Ideal prstena
R generisan elementima x1, . . . , xk oznaqavaemo sa (x1, . . . , xk), ili sa
〈x1, . . . , xk〉 ako prva oznaka moe dovesti do zabune ili zakomplikovati
zapis.
Znaqajan deo ovog rada oslanja se na Artinove prstene, specijalno i
na konaqne prstene. Ovo je najvixe izraeno u delovima gde ispitujemo
rod nekog grafa pridruenog prstenu. Istaknimo ovde jednu korisnu
teoremu o strukturi Artinovih prstena.
Teorema 1. [10, teorema 8.7]Artinov prsten R izomorfan je konaqnom
direktnom proizvodu R1 × · · · ×Rn Artinovih lokalnih prstena Ri.
Postoje neka razmimoilaenja raznih autora u definiciji lokalnog
prstena. Mi emo ovde slediti terminologiju iz [32]; komutativan
prsten sa jedinstvenim maksimalnim idealom je kvazilokalan; prsten
je lokalan ako je Neterin kvazilokalan. Artinovi lokalni prsteni
imaju relativno prostu strukturu, pa se gornja dekompozicija Arti-
novog prstena pokazuje korisnom pri svoenju odreenog komplikovani-
jeg problema na nii nivo. Specijalno, ovo vai i za sve konaqne
prstene. Nije texko videti da za konaqne lokalne prstene vai sledee
korisno tvrenje.
Tvrenje 2. [2, primedba 1.1]Neka je R konaqan lokalan prsten sa maksi-
malnim idealom M . Tada postoji prost broj p i pozitivni celi brojevi
t, l, k takvi da je char(R) = pt, |M | = pl, |R| = pk i char(R/M) = p.
Prsten R koji nije domen i ima konaqno mnogo delitelja nule mora
biti konaqan. Za takav prsten R vai |R| ≤ |Z(R)|2. Istaknimo ovu
teoremu u originalnoj verziji.
2
Teorema 3. [24, teorema 1]Komutativan prsten R sa n (n ≥ 1) pravih
delitelja nule mora biti konaqan i ne sadri vixe od (n+1)2 elemenata.
Veoma praktiqne rezultate u vezi konaqnih prstena dali su Kor-
bas i Vilijams. Oni su klasifikovali do na izomorfizam sve konaqne
komutativne prstene do reda p5, za prost broj p. Ova analiza je veoma
detaljna pa te rezultate neemo ovde eksplicitno navoditi. Po potrebi
emo se pozivati na pojedine delove tih radova. Celokupne rezultate
qitalac moe nai u radovima [19, 20].
1.1.2 Pojmovi iz teorije grafova
Pod pojmom graf u ovom radu uvek podrazumevamo prost neorijentisan
graf bez petlji. Graf G je ureen par (V,E), gde je E ⊆ [V ]2 i [V ]2 je skup
svih 2-elementnih podskupova od V . Ako su G i G′ grafovi, onda je G′
podgraf grafa G ako je V ′ ⊆ V i G′ ⊆ G. Ako G′ sadri sve ivice xy ∈ E
za x, y ∈ V ′ (ivicu {x, y} oznaqavamo sa xy), kaemo da je G′ indukovani
podgraf od G. Koristimo oznaku G[V ′] za indukovani podgraf generisan
sa V ′. Ako je F ⊆ [V ]2, onda je G − F := (V,E \ F ). Grafovi G i H su
izomorfni ako postoji bijekcija f : V (G)→ V (H) takva da su temena x i
y susedna u G akko su temena f(x) i f(y) susedna u H.
Stepen temena x, u oznaci deg(x), je broj temena u G susednih temenu
x i δ(G) = min{deg(v) | v ∈ V (G)} je minimalan stepen grafa G. Ako
sva temena grafa G imaju stepen k = δ(G), graf G je k-regularan. Dva
temena x i y u G su povezana ako postoji put u G qija je poqetna taqka x
i krajnja y. Ako su svaka dva temena iz G povezana, kaemo da je graf G
povezan. Rastojanje d(x, y) temena x, y ∈ G je duina najkraeg puta od x
do y ako su temena x i y povezana (d(x, y) =∞ ako takav put ne postoji).
Dijametar grafa G je
diam(G) = sup{d(x, y) | x, y ∈ V (G)}.
Ekscentricitet temena x je rastojanje do njemu najudaljenijeg temena,
3
e(x) = max{d(x, y) | y ∈ V (G)}. Ako je diam(G) konaqan, zanimljivo je
videti koliki je najmanji ekscentricitet temena u G. Temena u G naj-
manjeg ekscentriciteta obrazuju centar grafa G. Definixe se radijus
grafa G kao r(G) = min{e(x) | x ∈ V (G)}. Na taj naqin radijus grafa
je najmanji ekscentricitet, dok je dijametar povezanog grafa jednak na-
jveem ekscentricitetu nekog temena. Za povezane grafove dijametra d
i radijusa r vai r ≤ d ≤ 2r. Cikl (kontura) Cn duine n u G je put
x1— x2— · · · —xn—x1,
gde je xi 6= xj kada je i 6= j i n ≥ 3. Obim grafa G, u oznaci gr(G),
definixe se kao duina najkrae konture u G ako G sadri konturu; u
suprotnom gr(G) =∞. Povezan graf bez kontura je stablo. Kontura koja
prolazi kroz svako teme grafa taqno jednom je Hamiltonova kontura.
Graf G je Hamiltonov ako sadri Hamiltonovu konturu. Kontura koja
prolazi svaku ivicu grafa taqno jednom je Ojlerova kontura. Graf G
je Ojlerov ako sadri Ojlerovu konturu. Poznato je da je povezan ne-
orijentisan graf sa bar jednom ivicom Ojlerov akko su mu sva temena
parnog stepena.
Ako je E(G) = [V ]2, onda je G kompletan graf. Ako je skup V (G)
disjunktna unija skupova A i B takvih da je |A| = m, |B| = n, i tako
da su dva temena susedna akko ona pripadaju razliqitim skupovima,
onda je graf G kompletan bipartitan graf. Za kompletne i kompletno
bipartitne grafove koristimo oznake Kn i Km,n redom. U ovom radu
dopuxtamo da neki od m i n bude beskonaqan kardinal. Specijalno,
K1,n je zvezda graf.
Podskup S ⊆ V (G) je klika ako je indukovani podgraf generisan sa
S kompletan. Klika broj grafa G, u oznaci cl(G), je najvei ceo broj
r ≥ 1 takav da je Kr ⊆ G. Ako je Kr ⊆ G za svaki ceo broj r ≥ 1, onda
je cl(G) =∞. Hromatski broj grafa G, u oznaci χ(G), je minimalan broj
boja potrebnih za bojenje temena iz G tako da nikoja dva susedna temena
nisu obojena istom bojom. Uvek naravno vai cl(G) ≤ χ(G).
4
Neka je n nenegativan ceo broj i Sn orijentabilna povrx roda n. Rod
grafa G, u oznaci γ(G), je najmanje n tako da se G moe utopiti u Sn.
Ako se G utapa u povrx Sk, komponente od Sk − G zovemo oblastima.
Triangulacija povrxi Sk je utapanje u kome sve oblasti imaju granicu
koja se sastoji od taqno 3 ivice. Za konaqan povezan graf G roda g sa n
temena i m ivica vai Ojlerova formula
n−m+ f = 2− 2g, (1.1.1)
gde je f broj oblasti dobijenih (minimalnim) utapanjem G u povrx roda
g.
Ako se graf G moe predstaviti u ravni tako da mu se ivice ne
seku, onda je G roda 0 ili planaran; ako se isto to moe uraditi na
torusu, G je roda 1 ili toroidalan. Ako je H podgraf grafa G, onda je
γ(H) ≤ γ(G).
Kako je planarnost jedna od fundamentalnih osobina grafa, dobro
je znati koji grafovi su planarni a koji nisu. Poznata teorema Kura-
tovskog daje prostu karakterizaciju ovih grafova.
Teorema 4. [33]Graf je planaran akko ne sadri potpodelu od K5 ili K3,3.
Za ispitivanje roda nekog grafa qesto je pogodno posmatrati njegove
kompletne ili kompletno bipartitne podgrafove. Istaknimo ovde poz-
nate rezultate o rodu ovih grafova na koje emo se kasnije pozivati.
Oznaqimo sa dxe najmanji ceo broj koji je vei ili jednak od x. Vai
sledee tvrenje.
Tvrenje 5. [48, 49]
γ(Kn) =
⌈
(n− 3)(n− 4)
12
⌉
, ako je n ≥ 3. (1.1.2)
γ(Km,n) =
⌈
(m− 2)(n− 2)
4
⌉
, ako je m,n ≥ 2. (1.1.3)
5
Prema prethodnom tvrenju Kn je planaran za n ≤ 4 i toroidalan za
5 ≤ n ≤ 7. Grafovi K3,n (za 3 ≤ n ≤ 6) i K4,4 su toroidalni. Koristei
jednakost 1.1.1 i neke kombinatorne identitete moe se pokazati da vai
sledee tvrenje ([54, teorema 2.1]).
Tvrenje 6. Neka je G prost graf sa n temena, gde je n ≥ 3. Neka je γ(G) = g
i δ(G) minimalan stepen grafa G. Tada je
δ(G) ≤ 6 + 12g − 12
n
,
gde jednakost vai akko utapanje predstavlja triangulaciju povrxi.
Posledica 7. Neka je G prost graf sa n (n ≥ 3) temena.
1) Ako je γ(G) = 0, onda je δ(G) ≤ 5, tj. postoji teme x, takvo da je
deg(x) ≤ 5.
2) Ako je γ(G) = 1, onda je δ(G) ≤ 6, tj. postoji teme x, takvo da je
deg(x) ≤ 6. Xtavixe, δ(G) = 6 akko je G triangulacija torusa koja je
6-regularna.
6
GLAVA 2
TOTALNI GRAF KOMUTATIVNOG
PRSTENA
U ovoj glavi dati su neki novi rezultati u vezi sa totalnim grafom
komutativnog prstena. Najpre se diskutuje odreivanje radijusa to-
talnog grafa komutativnog prstena sa jedinicom R kada je ovaj graf
povezan. Dalje se razmatraju neka tipiqna raxirenja, kao xto su: prsten
polinoma, prsten formalnih redova nad R, idealizacija R-modula M i
prsten matrica Mn(R). Posmatraju se veze totalnih grafova prstena i
totalnih grafova njegovih raxirenja.
2.1 Definicija totalnog grafa
Neka je R komutativan prsten sa jedinicom i neka je Z(R) skup nje-
govih delitelja nule. Totalni graf T (Γ(R)) definixe se na sledei
naqin:
V (T (Γ(R))) := R, E(T (Γ(R))) := {{r1, r2} : r1 + r2 ∈ Z(R)},
gde V (T (Γ(R))) (E(T (Γ(R)))) oznaqava skup temena (ivica) grafa T (Γ(R)).
Graf T (Γ(R)) definisan je u radu [7]. U ovome radu radi lakxeg
zapisa umesto T (Γ(R)) koristiemo oznaku TΓ(R).
Karakteristike TΓ(R) prirodno zavise od toga da li je Z(R) ideal
u R ili ne, pa se u zavisnosti od toga njegove osobine uvek odvojeno
ispituju. Za prstene u kojima delitelji nule ne obrazuju ideal TΓ(R)
ima sloenu strukturu koja je sa algebarskog gledixta zanimljiva za
prouqavanje. Totalni graf TΓ(R) uvek sadri indukovane podgrafove
Reg(Γ(R)), Z(Γ(R)) i Nil(Γ(R)) sa temenima redom u Reg(R), Z(R) i Nil(R).
Ovi podgrafovi dosta govore o njegovoj strukturi.
Kada je Z(R) ideal u R, struktura TΓ(R) je relativno prosta i
moe se precizno opisati. Iz definicije neposredno sledi da je TΓ(R)
tada nepovezan i da predstavlja disjunktnu uniju kompletnog podgrafa
Z(Γ(R)) i podgrafa Reg(R). U tom sluqaju jedino je Reg(R) zanimljiv za
prouqavanje. Njegova struktura potpuno je opisana teoremom 8. Teoreme
9 i 10 su njene direktne posledice.
Teorema 8. [7, teorema 2.2]Neka je R komutativan prsten takav da je
Z(R) ideal u R, i neka je |Z(R)| = α i |R/Z(R)| = β (dopuxteno je da α i β
budu i beskonaqni kardinali).
1) Ako 2 ∈ Z(R), onda je Reg(R) unija β − 1 disjunktnih Kα.
2) Ako 2 /∈ Z(R), onda je Reg(R) unija (β − 1)/2 disjunktnih Kα,α.
Ovde naravno vai β − 1 = (β − 1)/2 = β, za beskonaqan kardinal β.
Teorema 9. [7, teorema 2.4]Neka je R komutativan prsten takav da je
Z(R) ideal u R. Tada
1) Reg(R) je kompletan akko R/Z(R) ∼= Z2 ili R ∼= Z3.
2) Reg(R) je povezan akko R/Z(R) ∼= Z2 ili R/Z(R) ∼= Z3.
3) Reg(R) (dakle i Z(Γ(R)) i TΓ(R)) je totalno nepovezan akko je R
domen i char(R) = 2.
8
Teorema 10. [7, teorema 2.5]Neka je R komutativan prsten takav da je
Z(R) ideal u R. Tada
1) diam(Reg(R)) = 0, 1, 2 ili ∞.
Specijalno, diam(Reg(R)) ≤ 2 ako je Reg(R) povezan.
2) gr(Reg(R)) = 3, 4 ili ∞.
Specijalno, gr(Reg(R)) ≤ 4 ako Reg(R) sadri konturu.
Kada delitelji nule ne qine ideal struktura totalnog grafa TΓ(R) ne
moe se tako precizno opisati kao u prvom sluqaju. Podgrafovi Z(Γ(R))
i Reg(Γ(R)) u ovom sluqaju nisu disjunktni, jer postoje x, y ∈ Z(R) takvi
da x + y /∈ Z(R). Temena −x ∈ Z(R) i x + y ∈ Reg(R) tada su susedna.
Primetimo da ovde mora da vai |Z(R)| ≥ 3. Istaknimo nekoliko bitnih
rezultata o strukturi TΓ(R) kada Z(R) nije ideal.
Teorema 11. [7, teorema 3.3]Neka je R komutativan prsten takav da Z(R)
nije ideal u R. Tada je TΓ(R) povezan akko je 〈Z(R)〉 = R (tj. R = 〈z1, . . . , zn〉
za neke z1, . . . , zn ∈ Z(R)). Specijalno, ako je R konaqan komutativan
prsten i Z(R) nije ideal u R, onda je TΓ(R) povezan.
Teorema 12. [7, teorema 3.4]Neka je R komutativan prsten takav da Z(R)
nije ideal u R i 〈Z(R)〉 = R (tj. TΓ(R) je povezan). Neka je n ≥ 2 najmanji
prirodan broj takav da je R = 〈z1, . . . , zn〉 za neke z1, . . . , zn ∈ Z(R). Tada
je diam(TΓ(R)) = n. Specijalno, ako je R konaqan komutativan prsten i
Z(R) nije ideal u R, onda je diam(TΓ(R)) = 2.
Posledica 13. [7, posledica 3.5]Neka je R komutativan prsten takav
da Z(R) nije ideal u R i pretpostavimo da je TΓ(R) povezan. Tada
1) diam(TΓ(R)) = d(0, 1).
2) Ako je diam(TΓ(R)) = n, onda je diam(Reg(Γ(R))) ≥ n− 2.
9
2.2 Radijus totalnog grafa
2.2.1 Z(R) je ideal u R
Kako je Z(R) uvek unija prostih ideala prstena R [32, teorema 2], u
sluqaju da je Z(R) ideal, on mora biti prost. Primetimo da je u tom
sluqaju indukovani podgraf Z(Γ(R)) kompletan; dakle,
r(Z(Γ(R))) = diam(Z(Γ(R))) = 1.
Meutim, tada je totalni graf TΓ(R) nepovezan jer teme x ∈ Z(R) nije
susedno ni sa jednim y ∈ Reg(R) (u suprotnom, x + y ∈ Z(R) dovodi do
kontradikcije y = x+y−x ∈ Z(R)). Kako je TΓ(R) nepovezan nema smisla
govoriti o njegovom radijusu, ali moemo razmotriti radijus podgrafa
regularnih elemenata. Struktura Reg(Γ(R)) opisana je u teoremi 8.
Prema teoremi 9, Reg(Γ(R)) je povezan akko je R/Z(R) ∼= Z2 ili R/Z(R) ∼=
Z3.
U prvom sluqaju Reg(Γ(R)) je kompletan graf Kα, gde je α = |Z(R)|, pa je
r(Reg(Γ(R))) = diam(Reg(Γ(R))) = 1 .
U drugom sluqaju Reg(Γ(R)) je kompletan bipartitan graf Kα,α, pa je
r(Reg(Γ(R))) = diam(Reg(Γ(R))) = 2 .
2.2.2 Z(R) nije ideal u R
Ako je R komutativan prsten takav da Z(R) nije ideal u R i ako
je TΓ(R) povezan, odreivanje njegovog radijusa postaje sloenije. Ako
delitelji nule ne obrazuju ideal, onda se za svaki prirodan broj n moe
konstruisati prsten Rn takav da je diam(TΓ(Rn)) = n [7, primer 3.8].
10
Kako sada postoje prsteni qiji totalni grafovi imaju proizvoljno ve-
liki dijametar, prirodno je postaviti pitanje xta se dexava sa radiju-
som totalnog grafa. Odgovor je pomalo neoqekivan, videemo da je radi-
jus uvek jednak dijametru. Kao motivacija mogu nam posluiti konaqni
komutativni prsteni kod kojih Z(R) nije ideal. Prema teoremi 12, ako
je R konaqan i Z(R) nije ideal u R, onda je diam(TΓ(R)) = 2.
Teorema 14. Neka je R konaqan komutativan prsten sa jedinicom u kome
Z(R) nije ideal. Tada je r(TΓ(R)) = 2.
Dokaz: Kako je d = diam(TΓ(R)) = 2, bie r = r(TΓ(R)) ≤ 2, pa je dovoljno
dokazati da je r 6= 1. Pretpostavimo suprotno, neka je r = 1. Tada
postoji x ∈ R takvo da je e(x) = 1, tj. x je susedno svakom temenu grafa.
Odavde je x ∈ Z(R) (x je susedno sa 0). Taqnije x ∈ Z(R)∗, jer bi u
suprotnom 1 bilo susedno sa 0, tj. R bi onda bio nula prsten.
Dalje, kako Z(R) nije ideal, postoje a, b ∈ Z(R) takvi da a+b ∈ Reg(R).
Pri tome vai da je x 6= a; u suprotnom, kako je e(x) = 1, teme x bilo
bi susedno i temenu b, xto dovodi do kontradikcije x+ b = a+ b ∈ Z(R).
Sliqno, x 6= b. Tada je oqigledno i x 6= a + b, jer su Reg(R) i Z(R)
disjunktni skupovi.
Teme c = −x + a + b ne pripada skupu {a, b, 0} i susedno je sa x. Vai
x+ c ∈ Z(R), odnosno x− x+ a+ b = a+ b ∈ Z(R), xto je u suprotnosti sa
pretpostavkom da a + b ∈ Reg(R). Ovim su ispitane sve mogunosti, pa
radijus mora biti 2.
Napomena 15. Prethodne teorema je posledica teoreme 16, ali je njen
dokaz ovde dat kao motivacija za opxtiji sluqaj.
Neka je R komutativan prsten sa jedinicom u kome Z(R) nije ideal.
Prema teoremi 11, TΓ(R) je povezan akko je R aditivno generisan svojim
deliteljima nule. Dakle 〈Z(R)〉 = R, tj. R = 〈z1, . . . , zn〉 za neke z1, . . . , zn ∈
Z(R). Prema teoremi 12 i posledici 13, diam(TΓ(R)) = n = d(0, 1) za min-
imalan broj takvih generatora. Dokaimo sada da je pod tim uslovima
11
radijus totalnog grafa jednak njegovom dijametru.
Teorema 16. Neka je R komutativan prsten sa jedinicom takav da Z(R)
nije ideal u R i neka je n ≥ 2 najmanji prirodan broj takav da je R =
〈z1, . . . , zn〉, za neke z1, . . . , zn ∈ Z(R). Tada je r(TΓ(R)) = n.
Dokaz: Iz datih uslova diam(TΓ(R)) = n, pa je svakako r = r(TΓ(R)) ≤ n.
Dovoljno je samo dokazati da nejednakost r ≤ n− 1 nije mogua.
Neka je r ≤ n − 1. Tada postoji x ∈ R takav da je e(x) ≤ n − 1, tj. za
svako y ∈ R, d(x, y) ≤ n−1. Specijalno, d(x, 1+x) ≤ n−1 i d(x, 1−x) ≤ n−1.
Neka je:
x— s1— s2— · · · — sk−2— 1 + (−1)k−1x,
put duine k − 1 ≤ n − 1 u TΓ(R). Tako dobijamo k − 1 delitelja nule
x+ s1 , s1 + s2 , . . . , sk−3 + sk−2 , sk−2 + 1 + (−1)k−1x, za koje vai:
〈x+ s1 , s1 + s2 , . . . , sk−3 + sk−2 , sk−2 + 1 + (−1)k−1x〉 ⊆ 〈Z(R)〉 = R.
Kako 1 ∈ 〈x+ s1 , s1+ s2 , . . . , sk−3+ sk−2 , sk−2+1+ (−1)k−1x〉, mora da vai:
〈x+ s1 , s1 + s2 , . . . , sk−3 + sk−2 , sk−2 + 1 + (−1)k−1x〉 = R.
Prsten R se dakle aditivno moe generisati sa k−1 delitelja nule xto
protivreqi pretpostavci o minimalnom broju generatora.
2.3 Totalni graf nekih raxirenja prstena
2.3.1 Prsten polinoma
Neka je R komutativan prsten i R[X] prsten polinoma. Primetimo
najpre da za delitelje nule uvek vai
Z(R) ⊆ Z(R[X]) ⊆ Z(R)[X].
12
Druga inkluzija moe biti prava, npr. 2+3x ∈ Z(Z6)[X]\Z(Z6[X]). Jasno
je da je i prva inkluzija prava. Poznata teorema Mek Koja potpuno
opisuje delitelje nule prstena polinoma: f(x) ∈ Z(R[X]) akko postoji
r ∈ R∗ takav da je rf(x) = 0. Dakle, osim xto koeficijenti moraju
biti delitelji nule, potrebno je i da ideal generisan njima ima ne-
nula anulator. U skladu sa tim kaemo da je R Mek Kojev prsten akko
za svaki konaqno generisani ideal I ⊆ Z(R) vai Ann(I) 6= 0. Dobro je
poznato da je prsten polinoma R[X] uvek Mek Kojev.
Struktura totalnog grafa prstena polinoma TΓ(R[X]) zavisie od
toga da li je Z(R[X]) ideal u R[X]. Prema [35, teorema 3.3] Z(R[X]) je
ideal u R[X] akko je R Mek Kojev prsten u kome je Z(R) ideal. Koristei
ovaj rezultat moemo opisati strukturu totalnog grafa prstena poli-
noma. Posmatramo dva sluqaja.
1) Z(R[X]) je ideal u R[X].
Oqigledno je onda podgraf delitelja nule Z(Γ(R[X])) kompletan. Tada
vai Z(R[X]) = Z(R)[X], pa je
R[X]/Z(R[X]) = R[X]/Z(R)[X] ∼= (R/Z(R)) [X].
Sa desne strane je prsten polinoma koji ne moe biti izomorfan ni sa
Z2 ni sa Z3. Prema teoremi 9, Reg(Γ(R[X])) nije povezan. Iz prethodne
analize moe se okarakterisati struktura totalnog grafa prstena poli-
noma u kojima delitelji nule qine ideal.
Teorema 17. Neka je R komutativan Mek Kojev prsten takav da je Z(R)
ideal u R. Tada je TΓ(R[X]) nepovezan. Indukovani podgraf Z(Γ(R[X])) je
kompletan, dok je Reg(Γ(R[X])) nepovezan.
Napomena 18. Kako je R[x] uvek Mek Kojev prsten i R[X,Y ] = R[X][Y ],
to se uz pretpostavke da je R Mek Kojev i da je Z(R) ideal u R, iz
prethodnog neposredno dobija da je Reg(Γ(R[X, Y ])) nepovezan.
2) Z(R[X]) nije ideal u R[X].
13
Lema 19. Neka je R komutativan prsten takav da Z(R) nije ideal u R.
Tada vai:
〈Z(R[X])〉 = R[X] akko 〈Z(R)〉 = R.
Dokaz: Neka je 〈Z(R[X])〉 = R[X]. Tada postoje polinomi f1(X), . . . , fn(X) ∈
Z(R[X]) takvi da je R[X] = 〈f1(X), . . . , fn(X)〉 i f1(X) + · · · + fn(X) = 1.
Odavde je z1 + · · ·+ zn = 1, gde su z1, . . . , zn konstantni koeficijenti ovih
polinoma. Kako je Z(R[X]) ⊆ Z(R)[X], svi koeficijenti ovih polinoma
su delitelji nule. Dakle, z1, . . . , zn ∈ Z(R). Odavde je R = 〈Z(R)〉 =
〈z1, . . . , zn〉. Drugi smer dokaza je oqigledan.
Kombinujui lemu 19 i teoreme 11, 12 i 16 dobijamo sledei rezul-
tat.
Teorema 20. Neka je R komutativan prsten takav da Z(R) nije ideal u R.
Tada je TΓ(R[X]) povezan akko je TΓ(R) povezan, tj. postoje z1, . . . , zn ∈ Z(R)
takvi da je R = 〈Z(R)〉 = 〈z1, . . . , zn〉. Ako je n minimalan broj takvih
generatora, onda je
diam(TΓ(R[X])) = r(TΓ(R[X])) = n .
2.3.2 Prsten formalnih redova
Iako srodni po konstrukciji, prsteni polinoma i formalnih redova
pored brojnih zajedniqkih osobina imaju i neke koje ih bitno razlikuju.
Takav je sluqaj i sa deliteljima nule – teorema Mek Koja ne mora da
vai u prstenu R[[X]]. U radu [23], Filds je prezentovao formalni
red sa invertibilnim koeficijentom koji je pravi delitelj nule. Ovim
primerom pokazano je da za razliku od prstena polinoma ovde ne mora
da vai Z(R[[X]]) ⊆ Z(R)[[X]]. Naravno, ne vai ni obratno. Uzrok
ovome su nilpotentni elementi. Naime, za redukovan prsten R, u radu
[25] pokazano je da f(X) ∈ Z(R[[X]]) akko postoji z ∈ Z(R)∗ takav da je
14
zf(X) = 0. Problematikom odreivanja dijametra grafova Γ(R[X]) i
Γ(R[[X]]) bave se radovi [11] i [35]. Autori su u potpunosti okarakter-
isali diam(Γ(R[X])) za proizvoljan prsten R i diam(Γ(R[[X]])) za reduko-
van prsten R. Za neredukovane prstene problem odreivanja dijametra
nije rexen.
Dalje razmatramo redukovan prsten R i analiziramo odgovarajui
totalni graf TΓ(R[[X]]). Prvo pitanje koje se prirodno postavlja je kada
je Z(R[[X]]) ideal u R[[X]]. Pretpostavimo zato da je Z(R) ideal u R.
Tada vai Z(R[[X]]) ⊆ Z(R)[[X]]. Ovde e vaiti jednakost akko je R
prebrojivo Mek Kojev, tj. svaki prebrojivo generisani ideal I ⊆ Z(R)
ima nenula anulator. Tako dolazimo do rezultata koji emo iskazati
u obliku sledee leme.
Lema 21. Neka je R redukovan, prebrojivo Mek Kojev prsten takav da
je Z(R) ideal u R. Tada je Z(R[[X]]) ideal u R[[X]] i vai Z(R[[X]]) =
Z(R)[[X]].
Pod ovim uslovima je
R[[X]]/Z(R[[X]]) = R[[X]]/Z(R)[[X]] ∼= (R/Z(R)) [[X]].
Desna strana nije izomorfna ni sa Z2 ni sa Z3, pa se moe formulisati
teorema sliqna onoj kod polinoma.
Teorema 22. Neka je R redukovan, prebrojivo Mek Kojev prsten takav
da je Z(R) ideal u R. Tada TΓ(R[[X]]) nije povezan, indukovani podgraf
Z(Γ(R[[X]])) je kompletan i Reg(Γ(R[[X]])) je nepovezan.
Na potpuno isti naqin kao i kod polinoma dokazuje se da za reduko-
vani prsten R u kome Z(R) nije ideal, vai
〈Z(R[[X]])〉 = R[[X]] akko 〈Z(R)〉 = R.
Tako dobijamo sledeu teoremu.
15
Teorema 23. Neka je R redukovan komutativan prsten takav da Z(R) nije
ideal u R. Tada je TΓ(R[[X]]) povezan akko je TΓ(R) povezan, tj. postoje
z1, . . . , zn ∈ Z(R) takvi da je R = 〈Z(R)〉 = 〈z1, . . . , zn〉. Ako je n ≥ 2 mini-
malan broj takvih generatora, onda je
diam(TΓ(R[[X]])) = r(TΓ(R[[X]])) = n.
2.3.3 Idealizacija
Tehnika idealizacije modula veoma je vana pri konstrukciji raznih
prstena sa deliteljima nule. Neka je R komutativan prsten iM R-modul.
Operacije na R×M definixemo sa:
(r1,m1) + (r2,m2) = (r1 + r2,m1 +m2) ,
(r1,m1)(r2,m2) = (r1r2, r1m2 + r2m1) .
Dobijeni komutativan prsten zovemo idealizacijom modulaM nad R, u oz-
naci R(+)M . Ovom konstrukcijom R-modul M moemo videti kao ideal
0(+)M prstena R(+)M . Kako je (0,m1)(0,m2) = (0, 0), to je ovaj ideal
nilpotentan indeksa 2. Primetimo takoe da identifikujui m ∈M sa
(0,m) ∈ R(+)M , sve elemente modula vidimo kao delitelje nule u ide-
alizaciji. Razni aspekti idealizacije detaljno su ispitani i opisani
u [5], dok se osobinama grafa Γ(R(+)M) bave radovi [9] i [12]. Pred-
met naxeg razmatranja je totalni graf TΓ(R(+)M). Prema [29, teorema
25.3], delitelji nule u idealizaciji su:
Z(R(+)M) = {(r,m) | r ∈ Z(R) ∪ Z(M), m ∈M} .
Osnovna pitanja kojima se bavimo su osobine totalnog grafa TΓ(R(+)M),
njegovih podgrafova Z(Γ(R(+)M)) i Reg(Γ(R(+)M)) i njihove veze sa odgo-
varajuim polaznim grafom TΓ(R) i pografovima Z(Γ(R)) i Reg(Γ(R)).
Oni se mogu manje ili vixe razlikovati pod odreenim uslovima. Kao
motivaciju pogledajmo nekoliko primera.
16
Primer 24. Idealizacija R(+)R, gde je R komutativan prsten i M = R
jedan R-modul.
Dokazaemo da osobine totalnog grafa prstena i njegove idealizacije
ostaju iste.
Neka je Z(R) ideal u R. Kao xto je ve poznato, TΓ(R) je nepovezan,
Z(Γ(R)) je kompletan dok je Reg(Γ(R)) povezan akko je R/Z(R) ∼= Z2 ili
R/Z(R) ∼= Z3. Kako je Z(R) ideal u R, oqigledno je i Z(R(+)R) =
Z(R)(+)R ideal u R(+)R. Dakle TΓ(R(+)R) je nepovezan i Z(Γ(R(+)R))
je kompletan. Kako je
(R(+)R)/(Z(R(+)R)) = (R(+)R)/(Z(R)(+)R) ∼= R/Z(R)(+)0 ∼= R/Z(R),
podgraf Reg(Γ(R(+)R)) bie povezan akko je Reg(Γ(R)) povezan.
Neka Z(R) nije ideal u R. Tada ni Z(R(+)R) = Z(R)(+)R nije ideal
u R(+)R. Odavde je TΓ(R(+)R) povezan akko je TΓ(R) povezan i vai
diam(TΓ(R(+)M)) = diam(TΓ(R)). Dokaz se moe izvesti poredei put
x— s1— · · · — sn— y u TΓ(R), sa putevima
(x, 0)— (s1, t1)— · · · — (sn, tn)— (y, 0), (x, a)— (s1, 0)— · · · — (sn, 0)— (y, b)
u TΓ(R(+)R). Za izvoenje videti dokaz [7, teorema 3.16].
Primer 25. Idealizacija Z[X]/(X2)(+)Z10.
Pokazaemo da se ovde osobine grafova TΓ(R) i TΓ(R(+)M) znaqajno
razlikuju. Prvi je nepovezan dok je drugi povezan.
Neka je R = Z[X]/(X2) = {a+ bx | a, b ∈ Z}, gde je x odgovarajua klasa
i M = Z10. Lako je proveriti da je M R-modul ako mnoenje definixemo
sa (a + bx)m := am. Skup delitelja nule Z(R) = {ax | a ∈ Z} je (glavni)
17
ideal u R, odakle je TΓ(R) nepovezan i Z(Γ(R)) kompletan. Takoe je
R/Z(R) ∼= Z, pa Reg(Γ(R)) nije povezan.
S druge strane Z(M) = P ∪Q, gde su P = 2Z+ 〈x〉 i Q = 5Z+ 〈x〉 prosti
ideali. Z(M) nije ideal u R. Primetimo da je ovde Z(R) ⊆ Z(M). Lako
se moe videti da onda ni skup delitelja nule
Z(R(+)M) = {(z,m) | z ∈ P ∪Q,m ∈ Z10},
nije ideal u R(+)M . Uzmimo, na primer z1 = (2, 0), z2 = (5, 0). Tada
z1, z2 ∈ Z(R(+)M), ali z1+z2 = (7, 0) ∈ Reg(R(+)M). Dalje, kako je (3, 5)z1+
(−1, 0)z2 = (1, 0), vai da je 〈Z(R)〉 = 〈z1, z2〉 = R(+)M , pa je TΓ(R(+)M)
povezan i diam(TΓ(R(+)M)) = 2. Podgraf Z(Γ(R(+)M) takoe je povezan
dijametra 2. Podgraf Reg(Γ(R(+)M) je kompletan, jer e za (s1,m1),
(s2,m2) ∈ Reg(Γ(R(+)M) vaiti s1 + s2 ∈ P , odnosno (s1 + s2,m1 + m2) ∈
Z(Γ(R(+)M)).
Prethodni primeri nas motivixu da vidimo pod kojim uslovima se
osobine totalnog grafa prstena R prenose na totalni graf idealizacije
R(+)M . Kako oqigledno uvek vai Z(R)(+)M ⊆ Z(R(+)M), prva pitanja
koja se postavljaju su uslovi pod kojima vai jednakost, kao i uslovi
pod kojima je taj skup ideal. U dokazima koristimo opxti rezultat
o idealima u idealizaciji [5, teorema 3.1]: Za ideal I prstena R i
podmodul N R-modula M , I(+)N je ideal u R(+)M akko je IM ⊆ N . Pri
tome je (R(+)M)/(I(+)N) ∼= (R/I)(+)(M/N). Vai sledea teorema.
Teorema 26. Neka je R komutativan prsten i M neki R-modul takav da
je Z(M) ⊆ Z(R). Tada su sledei uslovi ekvivalentni:
1) Z(R(+)M) je ideal u R(+)M .
2) Z(R) je ideal u R.
Pri tome vai Z(R)(+)M = Z(R(+)M).
18
Dokaz: Neka je najpre Z(R) ideal u R. Kako je Z(M) ⊆ Z(R), bie i
Z(R) ∪ Z(M) = Z(R), pa je Z(R(+)M) = Z(R)(+)M . Skup sa desne strane
sada je ideal prema [5, teorema 3.1].
Neka je sada Z(R(+)M) ideal u R(+)M , i neka su z1, z2 ∈ Z(R). Tada
(z1, 0), (z2, 0) ∈ Z(R(+)M) pa je i (z1+ z2, 0) ∈ Z(R(+)M). Odavde je z1+ z2 ∈
Z(R)∪Z(M) = Z(R). Sliqno, ako je r ∈ R i z ∈ Z(R), onda je (r, 0) ∈ R(+)M
i (z, 0) ∈ Z(R(+)M). Bie dakle (r, 0)(z, 0) = (rz, 0) ∈ Z(R(+)M), pa je i
rz ∈ Z(R) ∪ Z(M) = Z(R).
Teorema 27. Neka je R komutativan prsten takav da je Z(R) ideal u R i
neka je M R-modul za koji je Z(M) ⊆ Z(R). Tada je TΓ(R(+)M) nepovezan,
Z(Γ(R(+)M)) je kompletan, dok je Reg(Γ(R(+)M)) povezan akko je Reg(Γ(R))
povezan.
Dokaz: Iz prethodne teoreme i [7, teorema 2.1], dobijamo da je TΓ(R(+)M)
nepovezan i Z(Γ(R(+)M)) kompletan. Dalje,
(R(+)M)/(Z(R(+)M)) = (R(+)M)/(Z(R)(+)M) ∼= R/Z(R)(+)0 ∼= R/Z(R).
Odavde je Reg(Γ(R(+)M)) povezan akko je Reg(Γ(R)) povezan.
Sluqaj kada Z(R) nije ideal u R ispitan je u [7]. Autori su dokazali
da tada iz povezanosti TΓ(R) sledi povezanost grafa TΓ(R(+)M) i da
je diam(TΓ(R(+)M)) ≤ diam(TΓ(R)) ([7, teorema 3.17]). Pod dodatnim
uslovom Z(R)(+)M = Z(R(+)M) vai i vixe: TΓ(R(+)M) je povezan akko
je TΓ(R) povezan i tada je diam(TΓ(R(+)M)) = diam(TΓ(R)) ([7, teorema
3.16]).
2.3.4 Matrice
Mada ovde izlazimo iz okvira komutativne algebre, vredno je ispi-
tati i totalni graf prstena matrica Mn(R) nad komutativnim prstenom
19
R. Grafovi delitelja nule u nekomutativnom prstenu mogu se defin-
isati na razne naqine ali uobiqajena definicija pripada Redmondu [47].
Za grafove prstena matrica nad komutativnim prstenima videti [14].
Neka je R prsten. ZL(R) = {x ∈ R | xa = 0, za neko a ∈ R∗} je skup
levih delitelja nule, ZD(R) = {x ∈ R | bx = 0, za neko b ∈ R∗} skup desnih
delitelja nule i Z(R) = {x ∈ R | xy = 0 ili yx = 0 za neko y ∈ R∗} skup
delitelja nule u R. Redmond definixe usmereni i neusmereni graf,
u oznaci Γ(R), Γ(R) redom. Temena oba grafa su u Z(R)∗, s tim xto
je x → y u Γ(R) akko je xy = 0, dok je x— y u Γ(R) akko xy = 0 ili
yx = 0. Prema [47, teorema 2.3], graf Γ(R) je povezan akko ZL(R) =
ZD(R) i tada je diam(Γ(R)) ≤ 3, dok je Γ(R) uvek povezan i diam(Γ(R)) ≤
3, ([47, teorema 3.2]). Definisaemo totalni (neusmereni) graf TΓ(R)
nekomutativnog prstena R na isti naqin kao i u komutativnom sluqaju:
temena su svi elementi prstena R i dva temena x, y ∈ R su susedna akko
je x + y ∈ Z(R). Lako se moe pokazati da u sluqaju kada je Z(R) ideal
za ovako definisani totalni graf vae rezultati analogni onima u
komutativnim prstenima.
Neka je sada R komutativan prsten, n ≥ 2 i Mn(R) prsten kvadratnih
matrica nad R. Poznato je da u ovom prstenu vai A ∈ Z(Mn(R)) akko
det(A) ∈ Z(R) [16, teorema 9.1], pa je ZL(Mn(R)) = ZD(Mn(R)) = Z(Mn(R)).
Ovaj skup naravno nije ideal u Mn(R).
Neka su A,B ∈ Mn(R) proizvoljne matrice. Tada e postojati ma-
trica C ∈ Mn(R) takva da je A—C—B put u TΓ(Mn(R)). Zaista, za
A = [A↓1, . . . , A↓n], B = [B↓1, . . . , B↓n], biramo C = [−A↓1,−B↓2, 0, . . . , 0]. Za
ovako odabranu matricu C vai (A + C)↓1 = 0, (C + B)↓2 = 0. Odavde je
A+ C,C +B ∈ Z(Mn(R)). Na taj naqin dokazana je sledea teorema.
Teorema 28. Neka je R komutativan prsten. Tada je TΓ(Mn(R)) povezan i
diam(TΓ(Mn(R))) = 2.
20
GLAVA 3
TOTALNI GRAF MODULA
Ova glava bavi se uopxtenjem totalnog grafa prstena TΓ(R). Ako se na
sliqan naqin definixe totalni graf TΓ(M) proizvoljnog R-modula M
pokazaemo da je on njegova prirodna generalizacija.
Neka je R komutativan prsten sa jedinicom, uz standardne oznake R∗ =
R\{0} i Z(R)∗ = Z(R)\{0}. Neka je M proizvoljan R-modul, M∗ = M\{0}
i
T (M) = {m ∈M | rm = 0 , za neko r ∈ R∗}
podskup njegovih torzionih elemenata. Definixemo totalni graf mod-
ula TΓ(M) na sledei naqin:
V (TΓ(M)) :=M, E(TΓ(M)) := {{m1,m2} : m1 +m2 ∈ T(M)},
gde V (Γ) (E(Γ)) oznaqavaju temena (ivice) grafa Γ.
Za M = R, tj. kada prsten R posmatramo kao R-modul, T (M) = Z(R),
pa dobijamo totalni graf prstena TΓ(R) definisan u [7].
3.1 T (M) je podmodul modula M
Struktura totalnog grafa TΓ(M) moe se precizno opisati u sluqa-
jevima u kojima torzioni elementi qine podmodul. Poqnimo najpre od
krajnosti T (M) =M i T (M) = {0}.
Teorema 29. Totalni graf TΓ(M) je kompletan akko je T (M) =M .
Dokaz: Ako je T (M) = M , onda za svaka dva temena m1,m2 ∈ M vai
m1 + m2 ∈ T (M). Dakle, ona su susedna u TΓ(M). S druge strane, ako
je TΓ(M) kompletan, onda je svako teme grafa susedno sa 0. Odavde je
m = m+ 0 ∈ T (M), odakle sledi traeni rezultat.
Napomena 30. Uslov prethodne teoreme T (M) =M sigurno je zadovoljen
ako je Ann(M) 6= 0. Ilustrujmo ovo sledeim primerima.
Primer 31. Neka je R = Zn × Zm i M = Zn, R-modul sa operacijom
definisanom sa (a, b) ·m := am. Tada je Ann(M) 6= (0, 0) jer (0, b) ∈ Ann(M),
za svako b ∈ Zm. Dakle, TΓ(M) je kompletan.
Primer 32. Svaka konaqna Abelova grupa M je torzioni Z-modul. Ako
je specijalno, R = Z i M = Zn, R-modul sa uobiqajeno definisanim
mnoenjem, onda je TΓ(M) ∼= Kn. To znaqi da se svi konaqni kompletni
grafovi mogu realizovati kao totalni grafovi modula.
Pogledajmo kada se, za razliku od sluqaja kada je TΓ(M) kompletan,
dobija druga krajnost – njegova totalna nepovezanost. Ako je T (M) = {0},
onda su temena m1 i m2 susedna akko je m2 = −m1. Ako je pri tom M 6= 0,
TΓ(M) je nepovezan graf i njegove jedine ivice su one koje spajaju temena
mi i −mi.
Teorema 33. Neka je R komutativan prsten i neka je M R-modul. Tada je
TΓ(M) totalno nepovezan akko char(R) = 2 i M je bez torzije.
Dokaz: Ako je TΓ(M) totalno nepovezan, onda 0 nije susedno nijednom
temenu, tj. 0 + m = m /∈ T (M) za svako m ∈ M∗. Dakle T (M) = {0}, tj.
22
M je bez torzije. Dalje, kako je m+ (−m) = 0, iz totalne nepovezanosti
grafa sledi da je m = −m, tj. 2m = 0 za svako m ∈ M . Kako je T (M) =
{0}, mora da vai 2 = 0, odnosno char(R) = 2. Obratna implikacija je
oqigledna.
Lema 34. Neka je R komutativan prsten, T (M) podmodul R-modula M i
x ∈M\T (M). Tada vai: 2x ∈ T (M) akko 2 ∈ Z(R).
Dokaz: Neka je najpre 2 ∈ Z(R), tj. postoji r ∈ R∗ takvo da je 2r = 0.
Tada 2x ∈ T (M) za svako x, jer je r(2x) = (2r)x = 0.
Dalje, neka je 2x ∈ T (M). Kako x /∈ T (M), imamo da je x 6= 0 i za svako
r ∈ R: rx = 0⇒ r = 0. Kako 2x ∈ T (M), postoji a ∈ R∗ za koje je a(2x) = 0.
Odavde je (2a)x = 0. Kako x /∈ T (M), mora biti 2a = 0, tj. 2 ∈ Z(R).
Teorema 35. Neka je R komutativan prsten i M R-modul takav da je
T (M) njegov pravi podmodul. Tada je TΓ(M) nepovezan.
Dokaz: Ako je T (M) = {0}, onda teme 0 oqigledno nije susedno nijednom
temenu. Ako T (M) 6= {0}, onda su podgrafovi sa temenima iz T (M) i
M \ T (M) disjunktni. Zaista, ako bi x ∈ T (M) i y ∈ M \ T (M) bili
susedni, onda x+ y ∈ T (M). Budui da je T (M) podmodul, ovo dovodi do
kontradikcije y ∈ T (M).
Opis strukture grafa TΓ(M) kada je T (M) pravi podmodul sliqan je
opisu strukture grafa TΓ(R) kada je Z(R) ideal u R. Izneemo zato
dokaz u kratkim crtama.
Posmatramo koliqniqki modul M/T (M). Neka vai |T (M)| = α i
|M/T (M)| = β, gde dopuxtamo da α i β budu i beskonaqni kardinali.
Neka su x, y ∈ M \ T (M) takvi da je x + T (M) 6= y + T (M). Elementi
x+m1, x+m2 istog koseta x+ T (M) susedni su akko 2x ∈ T (M) (odnosno
2 ∈ Z(R) prema lemi 34). Tada x+m1 i y+m2 nisu susedni. U suprotnom,
dobijamo x− y = x + y − 2y ∈ T (M), odakle x + T (M) = y + T (M). Kako je
svaki koset kardinalnosti α, dobijamo da je TΓ(M) disjunktna unija β
kompletnih grafova Kα.
23
Ako 2 /∈ Z(R), onda elementi x+m1, x+m2 koseta x+ T (M) oqigledno
nisu susedni. Elementi x+m1, y+m2 razliqitih koseta susedni su akko
x + y ∈ T (M), odnosno y + T (M) = −x + T (M). Dobijamo da je podgraf
indukovan temenima iz M \ T (M) disjunktna unija (β − 1)/2 (= β, ako je
β beskonaqan) disjunktnih kompletno bipartitnih grafova Kα,α. Vai
dakle sledea teorema.
Teorema 36. Neka je R komutativan prsten i M R-modul takav da je
T (M) pravi podmodul. Neka je |T (M)| = α i |M/T (M)| = β.
1) Ako 2 ∈ Z(R), onda je TΓ(M) unija β disjunktnih kompletnih grafova
Kα.
2) Ako 2 /∈ Z(R), onda je TΓ(M) unija β − 1
2
disjunktnih kompletno bipar-
titnih grafova Kα,α i jednog kompletnog grafa Kα.
Primer 37. Uzmimo R-modul M = R⊕R.
1) Ako je R = Z4, onda je TΓ(M) unija 4 disjunktna K4.
2) Ako je R = Z9, onda je TΓ(M) disjunktna unija jednog kompletnog grafa
K9 i 4 kompletna bipartitna K9,9.
Teoreme 29 i 36 daju kompletan opis strukture totalnog grafa TΓ(M)
kada je T (M) podmodul. Prirodno se postavljaju pitanja kada je T (M)
podmodul modula M i u kakvoj je to vezi sa sluqajem kada je Z(R) ideal
u R. Kada je Z(R) = {0}, tj. ako je R domen, T (M) je naravno podmodul.
Dokazaemo da je T (M) podmodul i u nexto opxtijem sluqaju.
Teorema 38. Neka je R komutativan prsten. Ako je Z(R) = 〈z〉 glavni
ideal i z ∈ Nil(R), onda je T (M) podmodul modula M .
Dokaz: Neka je Z(R) = 〈z〉 i pretpostavimo da T (M) nije podmodul modula
M . Tada postoje m1,m2 ∈ T (M) takvi da m1 +m2 /∈ T (M). Neka za r1, r2 ∈
R∗ vai r1m1 = r2m2 = 0. Kako je onda r1r2(m1+m2) = 0 i m1+m2 /∈ T (M),
24
mora da vai r1r2 = 0, odnosno r1, r2 ∈ Z(R). Kako je z ∈ Nil(R), moemo
pretpostaviti da je r1 = azk i r2 = bzm za neke a, b /∈ Z(R). Ne umanjujui
opxtost, pretpostavimo da je k ≥ m. Tada za element br1 ∈ R∗ vai
br1(m1+m2) = 0, xto je u suprotnosti sa pretpostavkom da element m1+m2
nije torzion.
Napomena 39. Pod pretpostavkama prethodne teoreme sledi da je Z(R) =
Nil(R). Neka je R prsten polinoma Z[X]. Ako definixemo nestandardno
mnoenje u R sa p(X) ∗ q(X) = p(0)q(0), onda Z(R) = Nil(R) = 〈X〉. Tako su
ispunjeni uslovi teoreme 38. Ovo je takoe ispunjeno u prstenima Zpn
za svaki n ≥ 2 i prost broj p. Ovde je Z(R) = Nil(R) = 〈p〉.
Kada delitelji nule obrazuju ideal koji nije glavni, T (M) ne mora
biti podmodul, qak iako je Z(R) = Nil(R). Ilustrujmo to sledeim
primerom.
Primer 40. Neka je R lokalan prsten Z4[X]/(2X,X2). Lako se proverava
da je ovde Z(R) = Nil(R) = (2, x), gde je x odgovarajua klasa. Neka je
M = R/2R⊕R/xR i neka su m1 = (1+ 2R, xR),m2 = (2R, 1+ xR) ∈M . Tada
m1,m2 ∈ T (M), jer je 2m1 = xm2 = 0, dok m1+m2 = (1+2R, 1+xR) /∈ T (M).
3.2 T (M) nije podmodul modula M
Poqinjemo ovaj odeljak jednim interesantnim rezultatom koji povezuje
totalni graf modula sa grafom delitelja nule.
Teorema 41. Neka je R komutativan prsten takav da je diam(Γ(R)) = 3.
Tada T (R⊕R) nije podmodul R-modula R⊕R.
Dokaz: Kako je diam(Γ(R)) = 3 postoje r1, r2 ∈ Z(R)∗ za koje je d(r1, r2) = 3.
Neka je r1— s— t— r2 put u Γ(R). Elementi m1 = (r1, 0) i m2 = (0, r2)
25
pripadaju T (R ⊕ R) jer je sm1 = tm2 = 0, dok m1 +m2 = (r1, r2) /∈ T (M). U
suprotnom, ako (r1, r2) ∈ T (M) postoji r ∈ Z(R)∗ za koji je rr1 = rr2 = 0;
ovo dovodi do kontradikcije d(r1, r2) ≤ 2.
Neka je M R-modul. U prethodnom poglavlju videli smo da sluqaj
kada je Z(R) ideal u R moe, ali ne mora da implicira da je T (M)
podmodul u M . Isto vai i ako Z(R) nije ideal u R. Na primer, ako
M = Z6 posmatramo kao Z6-modul, onda jasno T (M)(= Z(R)) nije podmodul
u M (Z(R) nije ideal u R). S druge strane, ako M = Z6 posmatramo kao
modul nad R = Z6×Z6, sa mnoenjem (a, b) ·m = am, onda Z(R) nije ideal,
ali T (M) jeste podmodul, jer je Ann(M) = {(0, r) | r ∈ Z6}. Kao xto
ve znamo, u sluqaju kada Z(R) nije ideal u R, TΓ(R) je povezan akko je
〈Z(R)〉 = R. Ako je prsten R aditivno generisan svojim deliteljima nule,
povezanost grafa TΓ(R) imae suxtinsku ulogu u povezanosti grafa
TΓ(M). Razmatramo zato u ovom poglavlju sluqaj kada torzioni elementi
ne qine podmodul R-modula M niti delitelji nule qine ideal u R.
Lema 42. Neka je R komutativan prsten i M R-modul. Ako je jedinica
prstena R suma n delitelja nule, onda je svaki element modula M suma
najvixe n torzionih elemenata.
Dokaz: Oqigledno, ako je a ∈ Z(R) i x ∈ M , onda je ax ∈ T (M), pa za
svako m ∈M vai:
1 = z1 + · · ·+ zn ⇒ m = z1m+ · · ·+ znm.
Lemu 42 moemo preformulisati u nexto generalnijoj formi: ako je
R generisan (aditivno) svojim deliteljima nule, onda je svaki R-modul
generisan svojim torzionim elementima.
Teorema 43. Neka je R komutativan prsten i neka je M R-modul takav
da T (M) nije podmodul. Tada je TΓ(M) povezan akko je M generisan svojim
torzionim elementima.
26
Dokaz: Dokaimo da iz povezanosti grafa TΓ(M) sledi da je modul M
generisan torzionim elementima. Pretpostavimo da to nije taqno. Tada
postoji m ∈M koji nema reprezentaciju oblika m = m1+ · · ·+mn, gde su
mi ∈ T (M). Naravno m 6= 0, jer 0 ∈ T (M). Dokazaemo da tada ne postoji
put od 0 do m u TΓ(M). Ako je 0— s1— s2— · · · — sk—m put u TΓ(M),
onda su s1, s1 + s2, . . . , sk−1 + sk, sk +m, torzioni elementi i m se tada
moe predstaviti kao:
m = (sk +m)− (sk−1 + sk) + · · ·+ (−1)k−1(s1 + s2) + (−1)ks1.
Ovo je u kontradikciji sa pretpostavkom da m nije suma torzionih el-
emenata. Obratna implikacija moe se dokazati na sliqan naqin kao i
teorema 11, pa emo dokaz izostaviti.
Teorema 44. Neka je R komutativan prsten i M R-modul. Ako je TΓ(R)
povezan, onda je povezan i TΓ(M).
Dokaz: Neka je TΓ(R) povezan i neka je m ∈ M . Pokazaemo da postoji
put od 0 do m u TΓ(M). Neka je:
0— r1— r2— · · · — rk— 1 (3.2.1)
put od 0 do 1 u TΓ(R). Tada su r1, r1+r2, . . . , rk+1 ∈ Z(R). Kako za r ∈ Z(R)
i m ∈M vai rm ∈ T (M), ,,mnoenjem” puta 3.2.1 sa m dobijamo da je:
0— r1m— r2m— · · · — rkm—m (3.2.2)
put od 0 do m u TΓ(M). Kako se svaka dva temena mogu spojiti preko 0,
TΓ(M) je povezan.
Napomena 45. Primetimo da prema prethodnom dokazu vai sledea
osobina: ako je d(0, 1) = n u TΓ(R), onda je d(0,m) ≤ n u TΓ(M), za svako
m ∈M .
27
Teorema 46. Ako je svaki element modula M suma najvixe n torzionih
elemenata, onda je diam(TΓ(M)) ≤ n. Ako je n najmanji takav broj, onda je
diam(TΓ(M)) = n.
Dokaz: Dokaimo najpre da je pod datim uslovima rastojanje prozvoljnog
elementa m do 0 najvixe n. Neka je m = m1 + · · · + mn, gde mi ∈ T (M).
Tada za ai = (−1)i+n(m1 + · · ·+mi),
0— a1— a2— · · · — an,
je put od 0 do m duine n u TΓ(M). Neka x, y ∈M . Dokazujemo da je onda
d(x, y) ≤ n. Dokaz izvodimo koristei puteve (A) od 0 do x − y i (B) od
0 do x+ y. Neka su to putevi:
(A) x− y— s1— s2— · · · — sn−1— 0 ,
(B) x+ y— t1— t2— · · · — tn−1— 0 .
Prema prethodnom, duina tih puteva je najvixe n. U zavisnosti od
toga da li je n paran ili neparan, dobijamo puteve (A′) ili (B′) od x do
y duine n.
(A′) x— (s1 − y)— (s2 + y)— · · · — (sn−1 − y)— y ,
(B′) x— (t1 + y)— (t2 − y)— · · · — (tn−1 − y)— y .
Neka je sada n najmanji takav broj i neka je m = m1 + · · · +mn najkrae
predstavljanje elementa m kao sume torzionih. Dokaimo da je d(0,m) =
n. Prema prethodnom je d(0,m) ≤ n. Pretpostavimo zato da je d(0,m) =
k < n i neka je 0— s1— s2— · · · — sk−1—m put u TΓ(M). Koristei
isti argument kao i u dokazu teoreme 61, dolazimo do kontradikcije –
reprezentacije elementa m kao sume k < n torzionih elemenata. Ovim
je teorema dokazana.
Posledica 47. Neka je R komutativan prsten takav da Z(R) nije ideal
u R, 〈Z(R)〉 = R i neka je M R-modul. Ako je diam(TΓ(R)) = n, onda je
diam(TΓ(M)) ≤ n. Specijalno, ako je R konaqan, onda je diam(TΓ(M)) ≤ 2.
28
Dokaz: Direktno sledi kombinujui lemu 42 i teoremu 46. Posebno, ako
je R konaqan komutativan prsten u kome Z(R) nije ideal, onda je prema
teoremi 12, diam(TΓ(R)) = 2.
Kao xto je ve reqeno, za svako n ≥ 2 moe se konstruisati komutati-
van prsten Rn, u kome Z(Rn) nije ideal, takav da je diam(TΓ(Rn)) = n. To
znaqi da i TΓ(M) moe imati dijametar n za svako n, ako Rn posmatramo
kao Rn-modul.
Neka je TΓ(M) povezan i 〈Z(R)〉 = R. Iz sledeeg primera vidimo da
onda diam(TΓ(M)) ne mora zavisiti od broja generatora iz Z(R).
Primer 48. Neka je R komutativan prsten i neka su z1, z2 ∈ Z(R) takvi
da je z1 + z2 = 1. Neka je M = R/z1R⊕R/z2R.
Ako je z1z2 6= 0, onda z1z2 ∈ Ann(M), odakle je M torzioni modul.
Dakle diam(TΓ(M)) = 1.
Ako je z1z2 = 0, onda se mnoenjem jednakosti z1 + z2 = 1 sa z1 dobija
z21 = z1. Odavde z1 mora biti idempotentan. Neka su m1 = (1 + z1R, 0) i
m2 = (0, 1 + z2R) elementi iz T (M). Dokazujemo da tada m1 +m2 /∈ T (M).
Ako je r(1+z1R, 1+z2R) = 0, onda r ∈ z1R∩z2R, tj. r = z1a = z2b. Mnoenjem
poslednje jednakosti sa z1, dobija se z21a = 0. Kako je z1 idempotentan,
vai r = z1a = 0. Dakle T (M) nije podmodul modulaM , pa prema teoremi
46, mora da vai diam(TΓ(M)) = 2.
29
GLAVA 4
QISTI GRAF
U ovoj glavi, R je komutativan prsten sa jedinicom, U(R) skup nje-
govih invertibilnih elemenata, Id(R) skup njegovih idempotentnih ele-
menata, Z(R) skup njegovih delitelja nule. Zbog jednostavnosti uvodimo
oznaku UI(R) = U(R) ∪ Id(R). Za svaki prirodan broj n, Un(R) oznaqava
skup onih elemenata prstena R koji se mogu predstaviti u obliku sume
k ≤ n invertibilnih elemenata, dok U′(R) oznaqava sve elemente iz R
koji se mogu predstaviti kao konaqne sume invertibilnih, tj. U′(R) =
∪∞n=1Un(R). Prsteni generisani svojim invertibilnim elementima pred-
met su mnogih istraivanja. R je dobar, ili prema Rafaelu ([44]),
S-prsten, ako je R = U′(R). Prsten je prema Vamosu ([51]) n-dobar,
ili prema Henriksenu ([27]), (S, n)-prsten, ako je R = Un(R). Prema
Nikolsonu ([38]) prsten je qist ako je svaki njegov element zbir invert-
ibilnog i idempotentnog. Hiao i Tong u [56] generalixu ove prstene
uvodei pojam n-qistih i Σ-qistih prstena u kojima je redom svaki el-
ement zbir idempotentnog i n invertibilnih, odnosno idempotentnog i
konaqno mnogo invertibilnih. Klasa n-qistih prstena sadri qiste
i n-dobre prstene, dok klasa Σ-qistih prstena sadri sve prethodno
opisane klase. Izmeu ostalog, Hiao i Tong pokazuju da je grupni
prsten Z(p)G, gde je G cikliqna grupa reda 3, 2-qist za svaki prost
broj p 6= 2. Kako su Han i Nikolson ranije u [26] pokazali da grupni
prsten Z(7)G nije qist, imamo prsten koji je 2-qist ali nije qist. S
druge strane, Kamilo i Ju su u [17] pokazali da svaki qist prsten u
kome je 2 invertibilan mora biti i 2-dobar, dakle i 2-qist. Od ostalih
rezultata iz ove oblasti pomenimo jox rezultat Henriksena, koji je u
[27] pokazao da je Mn(R) 3-dobar za proizvoljan prsten R i za svako n ≥ 2.
Glavna ideja u ovoj glavi je da komutativnom prstenu sa jedinicom
pridruimo graf na naqin koji e omoguiti bolje razumevanje svo-
jstava gore pomenutih klasa prstena. Zadraemo se ovde na komu-
tativnom sluqaju mada se isti graf moe definisati i za nekomuta-
tivne prstene. Definixemo qisti graf CΓ(R) komutativnog prstena R
na sledei naqin:
V (CΓ(R)) := R, E(CΓ(R)) := {{r1, r2} : r1 + r2 ∈ UI(R)},
gde V (Γ) (E(Γ)) oznaqava skup temena (ivica) grafa Γ.
Veza sa qistim prstenima je lako vidljiva. Neka je R qist prsten.
Tada je CΓ(R) povezan i diam(CΓ(R)) ≤ 4. Naime, ako su x, y ∈ R, onda je
x = u1 + e1, y = u2 + e2, za neke u1, u2 ∈ U(R), e1, e2 ∈ Id(R). Tada je
x = u1 + e1 — (−u1)— 0— (−u2)— u2 + e2 = y
put od x do y u CΓ(R), odakle sledi tvrenje. Ovde zapravo vai taqniji
rezultat, dokazaemo da je diam(CΓ(R)) = 2 za svaki qisti prsten R.
U delu 4.1 bavimo se pitanjima vezanim za strukturu ovog grafa.
Ispitujemo pod kojim uslovima je CΓ(R) kompletan i da li moe biti
kompletan bipartitan. Dokazujemo da je CΓ(R) stablo akko je R = Z2,
kao i da je njegov obim 3, 4 ili ∞. Glavni rezultati nalaze se u delu
4.2. Dokazujemo da je CΓ(R) povezan akko je R aditivno generisan svojim
idempotentnim i invertibilnim elementima. Nalazimo i dokazujemo
kriterijum kada je diam(CΓ(R)) konaqan i specijalno, kada je jednak 2.
31
Izmeu ostalog, dokazujemo da svi komutativni poluperfektni i qisti
prsteni imaju povezan qisti graf dijametra 2. U delu 4.3 bavimo se
pitanjem roda grafa CΓ(R), kada je R konaqan prsten. Dokazujemo da
je qisti graf planaran akko je R izomorfan jednom od prstena: F2, F3,
F4, Z4 ili F2[X]/(X2), kao i da je toroidalan akko je R izomorfan jed-
nom od prstena: F5, F7, Z8, F2[X]/(X3), F2[X, Y ]/(X, Y )2, Z4[X]/(2X,X2),
Z4[X]/(2X,X2 − 2), F2 × F3, F2 × Z4, F2 × F4 ili F2 × F2[X]/(X2).
4.1 O strukturi grafa CΓ(R)
Glavne texkoe pri opisu strukture grafa CΓ(R) potiqu od nepravil-
nosti zbira idempotentnih i invertibilnih elemenata. Qak i zahtev da
UI(R), ili njegovi podskupovi U(R) ili Id(R), budu zatvoreni za zbir
ispostavlja se kao prejak. Ipak, u nekim specijalnim sluqajevima (na
primer ako je prsten R kvazilokalan), struktura grafa CΓ(R) moe se
preciznije opisati. Pogledajmo najpre kada je CΓ(R) kompletan.
Teorema 49. CΓ(R) je kompletan akko je R polje ili Bulov prsten.
Dokaz: Pretpostavimo da je CΓ(R) kompletan i da R nije ni polje ni
Bulov prsten. Vai: R = U(R) ∪ Id(R) (CΓ(R) je kompletan, pa je svako
teme susedno sa 0), Id(R) 6= R (R nije Bulov prsten) i R \ {0} 6= U(R)
(R nije polje). Odavde vidimo da postoje x ∈ U(R) \ Id(R) i y ∈ Id(R) \
(U(R) ∪ {0}). Ako je xy ∈ U(R), onda je y ∈ U(R), kontradikcija. Dakle
xy ∈ Id(R), pa je (xy)2 = xy. Kako je x ∈ U(R) i y ∈ Id(R), vai xy = y.
Odavde y(1−x) = 0, i kako y 6= 0, 1−x /∈ U(R), mora da vai 1−x ∈ Id(R).
Tada x = 1− (1− x) ∈ Id(R), xto je u kontradikciji sa izborom elementa
x.
Obratna implikacija je trivijalna.
Tvrenje 50. Neka je R komutativan prsten. Ako je char(R) 6= 2, onda
CΓ(R) nije kompletan bipartitan graf i nije stablo.
32
Dokaz: Oqigledno, jer CΓ(R) sadri trougao: (−1)— 0— 1— (−1).
Teorema 49 pokazuje da je za prsten R karakteristike 2, koji nije
polje, CΓ(R) kompletan akko je R Bulov prsten. S druge strane, ako je
char(R) = 2, CΓ(R) moe (ali ne mora) biti kompletan bipartitan graf.
Ilustrujemo to sledeim primerima.
Primer 51. R = Z2[X1, . . . , Xn]/(X21 , . . . , X2n). Oznaqimo sa xi odgovarajue
klase elemenata Xi, i neka je xα = xα11 · · · xαnn , αi ∈ { 0, 1}. Lako se moe
pokazati da je polinom
f = a0 +
∑
α∈{0,1}n
aαx
α , a0, aα ∈ { 0, 1},
invertibilan akko je a0 = 1. Prsten R je karakteristike 2 i njegovi je-
dini idempotenti su 0 i 1. Lako se proverava da za f, g ∈ R: f +g ∈ U(R)
akko je taqno jedan od njih invertibilan. Zakljuqujemo da je CΓ(R) ∼=
K2n,2n; dva dela particije obrazuju invertibilni i neinvertibilni el-
ementi.
Napomena 52. Primetimo da ovde moemo posmatrati i prsten
S = Z2[X1, X2, . . . ]/(X21 , X22 , . . . ).
Tada je CΓ(S) beskonaqan kompletan bipartitan graf Kα,α.
Primer 53. Neka je R = Z2 × Z2[X]/(X2). R je prsten karakteristike 2
kod koga je Id(R) = {(0, 0), (0, 1), (1, 0), (1, 1)} i U(R) = {(1, 1), (1, 1 + x)} (x
je klasa od X). CΓ(R) nije kompletan (x2 = 0 6= x), a nije ni kompletan
bipartitan jer sadri trougao (0, x)— (1, x)— (0, 1 + x)— (0, x).
Teorema 54. CΓ(R) je stablo akko je R ∼= Z2.
33
Dokaz: Ako je char(R) 6= 2, CΓ(R) sadri trougao: 0— 1— (−1)— 0.
Pretpostavimo zato da je char(R) = 2 i da je CΓ(R) stablo. Ako su
x, y ∈ R susedni, onda su 1 + x, 1 + y takoe susedni. Kako je x susedno
sa 1 + x i y susedno sa 1 + y, dobijamo cikl 1 + x—x— y— 1 + y— 1 + x.
Ovo je nemogue, pa mora da vai y = 1 + x. Dakle, x je susedno sa y
akko je y = 1 + x. Kako je CΓ(R) povezan, zakljuqujemo da R sadri samo
0 i 1.
Teorema 55. Neka je R komutativan prsten.
1) Ako je char(R) 6= 2, onda je gr(CΓ(R)) = 3.
2) Ako je char(R) = 2, onda je gr(CΓ(R)) = 3, 4 ili ∞.
Dokaz:
1) Imamo prethodno pomenutu konturu 0— 1— (−1)— 0.
2) Neka najpre UI(R) = {0, 1}. U tom sluqaju jedine ivice CΓ(R) su
ivice koje spajaju temena a i a + 1, za a ∈ R. Graf dakle nema kontura,
pa je gr(CΓ(R)) =∞.
Ako je |UI(R)| ≥ 3, postoji a ∈ UI(R) \ {0, 1}. Tada imamo konture
0— 1— 1+a— a— 0 ili 0— 1— a— 0, u sluqaju da 1+a ∈ UI(R). Odavde
je gr(CΓ(R)) = 4 ili gr(CΓ(R)) = 3.
Primer 56. Kao ilustraciju navodimo sledee primere:
1) gr(CΓ(R)) = 3, ako je R = Z2 × Z2;
2) gr(CΓ(R)) = 4, ako je R = Z2[X]/(X2);
3) gr(CΓ(R)) =∞, ako je R = Z2[X].
4.2 Povezanost i dijametar grafa CΓ(R)
Pitanje koje nas najvixe zanima u ovom delu je pitanje povezanosti
grafa CΓ(R) i raqunanje njegovog dijametra. Mada deluje neoqekivano,
dobija se da je graf CΓ(R) konaqnog prstena R uvek povezan, dijametra
34
najvixe 2. Kod prstena koji nisu konaqni mogunosti su vee. Pogleda-
jmo kao motivaciju najprostiji primer, prsten celih brojeva. Z je Σ-
qist i nije n-qist ni za jedno n. Moemo rei i da je Z dobar prsten
koji nije i n-dobar. Ovde je UI(Z) = {−1, 0, 1}. Dakle, jedina temena
susedna temenu m ∈ Z su −m, 1 − m i −1 − m. Rastojanje dva temena
d(m,n) bie dakle jednako ||m| − |n|| ili ||m| − |n|| + 1. Tako je CΓ(Z)
(Sl.1) povezan i nema konaqan dijametar.
Q
Q
Q
Q
´
´
´
´t
t t t
t t t
q q q
q q q
0
1 −2 3
−1 2 −3
Slika 1. CΓ(Z)
Dokaimo sada teoremu o povezanosti grafa CΓ(R) za proizvoljan ko-
mutativan prsten R. U tom cilju uvodimo pojam (k,m)-qistih elemenata.
Definicija 57. Neka je m pozitivan ceo broj. Element x ∈ R je (k,m)-
qist ako je x = e1 + · · ·+ ek + u1 + · · ·+ um, gde su ei ∈ Id(R) i uj ∈ U(R).
Na taj naqin qisti elementi su (1, 1)-qisti, n-qisti su (1, n)-qisti,
dok su n-dobri (0, n)-qisti. Kada to ne dovodi do zabune (k,m)-qist
element x zapisivaemo u obliku x =
∑n
i=1 xi, gde su xi ∈ UI(R) i n = k+m.
Neka je:
En(R) =
{
k∑
i=1
xi : xi ∈ UI(R) , k ≤ n
}
, E(R) =
∞⋃
n=1
En(R).
Prsten R je En-prsten za neko n ako je R = En(R); prsten R je E-prsten
ako je R = E(R). Na taj naqin E-prsteni su upravo oni prsteni koji
su aditivno generisani svojim idempotentima i invertibilnim ele-
mentima. Prsten celih brojeva Z je primer E-prstena koji nije En-
prsten ni za jedno n; dakle, klasa En-prstena je prava podklasa klase
35
E-prstena. Ovi pojmovi u bliskoj su vezi sa pitanjem povezanosti i pi-
tanjem konaqnog dijametra CΓ(R). Naime CΓ(R) bie povezan akko je R
E-prsten dok e njegov dijametar biti konaqan akko R je En-prsten, za
neko n.
Da bi ovo dokazali bie nam potrebno nekoliko lema. U dokazima
ovih lema koristimo qinjenicu da su invertibilni i idempotentni el-
ementi qisti. To je jasno za invertibilne elemente, dok e za e ∈ Id(R)
vaiti e = (2e− 1)+ (1− e), gde je 2e− 1 ∈ U(R). Ovo predstavljanje idem-
potenta je jednoznaqno, tj. ako je e = u + f , za neke u ∈ U(R) i f ∈ Id(R),
onda je u = 2e− 1 i f = 1− e. Za dokaz videti [4, lema 6].
Lema 58. Neka je R komutativan prsten i x =
∑m
i=1 ei, gde su ei ∈ Id(R).
Tada postoji put od x do 0 u CΓ(R).
Dokaz: Put od x do 0 dobijamo koristei poznatu osobinu idempotenata:
e ∈ R je idempotentan akko je 1− e idempotentan. Jedan put je:
m∑
i=1
ei—
(
−
m∑
i=2
ei
)
—
(
1 +
m∑
i=3
ei
)
—
(
−
m∑
i=3
ei
)
—
(
1 +
m∑
i=4
ei
)
— · · ·
· · · — (1 + em) — (−em)— 1— 0.
Primetimo da je d (
∑m
i=1 ei, 0) ≤ 2m− 1.
Lema 59. Neka je R komutativan prsten i x, y ∈ R. Ako je d(x+ y, 0) = r,
onda je d(x, y) ≤ r + 1.
Dokaz: Neka je (x+ y) — s1 — s2 — · · · — sr−1 — 0 put duine r u CΓ(R).
Tada je
x — (y + s1) — (−y + s2) — · · · — ((−1)r−1y + sr−1) — (−1)ry — (−1)r+1y,
takoe put u CΓ(R). Odavde je d(x, y) ≤ r ako je r paran i d(x, y) ≤ r + 1,
ako je r neparan.
36
Lema 60. Neka je R komutativan prsten i neka je x ∈ R takav da d(x, 0) =
n u CΓ(R). Tada postoje k i m takvi da je x (k,m)-qist. Preciznije, tada
je:
x =
k+m∑
i=1
xi, gde su xi ∈ UI(R) i k +m ≤
[
3n
2
]
.
Dokaz: Neka je 0 — s1 — s2 — · · · — sn−1 — x put duine n u CΓ(R).
Tada s1, s1 + s2, . . . , sn−1 + x pripadaju UI(R). Sam element x moe se
predstaviti u obliku:
x = (x+ sn−1)− (sn−1 + sn−2) + · · ·+ (−1)n−1s1.
Ovo meutim nije traena reprezentacija, jer u sluqaju da je si−1 + si
idempotentan, to ne mora biti i element −(si−1 + si). Takvih sabiraka
ima najvixe
[n
2
]
i svaki od njih moe se zameniti sa dva sabirka e-
ljenog oblika stavljajui −(si−1 + si) = 1− (si−1 + si) + (−1).
Teorema 61. Neka je R komutativan prsten. Tada je CΓ(R) povezan akko
je R E-prsten.
Dokaz: Pretpostavimo najpre je R E-prsten, tj. da se svaki element
prstena R moe predstaviti u obliku sume elemenata iz UI(R) i neka su
x, y ∈ R. Prema lemi 59, dovoljno je pokazati da postoji put od x+ y do
0. Neka je x+y (m,n)-qist, odnosno x+y =
n∑
i=1
ui+
m∑
j=1
ej , gde su ui ∈ U(R),
ej ∈ Id(R). Tada u CΓ(R) postoji sledei put:
x+ y =
n∑
i=1
ui +
m∑
j=1
ej —
(
−
n∑
i=2
ui −
m∑
j=1
ej
)
—
(
n∑
i=3
ui +
m∑
j=1
ej
)
— · · ·
· · · — (−1)n−1
(
un +
m∑
j=1
ej
)
— (−1)n
m∑
j=1
ej.
Ako je n paran, onda primenom leme 58 ovaj put moemo produiti do 0.
Ako je n neparan, ovaj put takoe moemo produiti do 0 jer je −∑mj=1 ej
susedno sa
∑m
j=1 ej.
37
Pretpostavimo sada da je CΓ(R) povezan i neka je x 6= 0 proizvoljan
element prstena R. Kako je graf povezan, postoji put od x do 0 u CΓ(R) i
neka je duina tog puta jednaka n. Prema lemi 60, postoje k i m takvi da
je x (k,m)-qist. Dakle, proizvoljan element prstena R je zbir konaqno
mnogo invertibilnih i idempotentnih elemenata, tj. R je E-prsten.
Teorema 62. Neka je R komutativan prsten. Tada je diam(CΓ(R)) konaqan
akko R je En-prsten za neko n.
Dokaz: Pretpostavimo da je diam(CΓ(R)) = d, i neka je 0 6= x ∈ R. Tada je
d(x, 0) ≤ d. Prema lemi 60, x =∑ni=1 xi, gde su xi ∈ UI(R) i n ≤ [3d2 ].
Neka je sada R En-prsten, za neko n. Naravno, tada je R i E-prsten,
pa je CΓ(R) povezan prema prethodnoj teoremi. Neka x, y ∈ R. Kako
je R En-prsten, element x + y je (k,m)-qist za neke k i m takve da je
k + m ≤ n. Prema lemi 58 i prema dokazu teoreme 61, duina puta
od x + y =
∑k
j=1 ej +
∑m
i=1 ui do 0 je najvixe 2k + m. Prema lemi 59,
d(x, y) ≤ 2k +m+ 1, odakle je diam(CΓ(R)) konaqan.
Posledica 63. Neka je R komutativan prsten i R[X] prsten polinoma.
Tada je CΓ(R[X]) nepovezan.
Dokaz: Element X oqigledno se ne moe predstaviti u obliku sume idem-
potenata i invertibilnih elemenata iz R[X]. Tvrenje neposredno sledi
primenom teoreme 61.
Teorema 64. Neka je R komutativan prsten. Tada: diam(CΓ(R[[X]])) je
konaqan akko je diam(CΓ(R)) konaqan.
Dokaz: Neka je diam(CΓ(R)) = n < ∞, i neka su f = a0 +
∑∞
i=1 aiX
i i
g = c0 +
∑∞
i=1 ciX
i ∈ R[[X]]. Pokazaemo da postoji put od f do g u
CΓ(R[[X]]) duine ne vee od 2n+ 2. Kako je CΓ(R) povezan, postoji neki
put a0 — b1 — b2— · · · — bn−1 — 0 od a0 do 0 u CΓ(R). Pomou ovog puta
i koristei qinjenicu da je formalni red invertibilan akko je takav
38
njegov konstantni qlan, nalazimo put od f do 1 duine najvixe n + 1 u
CΓ(R[[X]]):
a0 + S— (b1 − S) — (b2 + S) — · · · —
(
bn−1 + (−1)n−1S
)
— (−1)nS — 1,
gde je S =
∑∞
i=1 aiX
i. Ako je c0 — d1 — d2— · · · — dm — 0 put od c0 do 0
u CΓ(R), na isti naqin nalazimo put od g do 1 u CΓ(R[[X]]), odakle sledi
tvrenje. Obratna implikacija je trivijalna.
Teorema 65. Neka je R komutativan prsten takav da je diam(CΓ(R)) = n.
Ako je S homomorfna slika prstena R, onda je diam(CΓ(S)) ≤ n.
Dokaz: Oqigledno, jer homomorfizam invertibilne elemente slika u
invertibilne a idempotentne u idempotentne.
Napomena 66. Obratno ne mora da vai. Kao kontraprimer moemo
uzeti prsten polinoma R[X], gde je R En-prsten.
Teorema 67. Neka je R kvazilokalan prsten i x, y ∈ R. Tada postoji z ∈ R
takav da je x+ z ∈ { 0, 1} i z + y ∈ U(R).
Dokaz: Neka je M maksimalni ideal kvazilokalnog prstena R i x, y ∈ R.
Ispitajmo sve mogunosti.
1) x, y ∈M : z = 1− x.
2) x ∈M , y /∈M (ili x /∈M , y ∈M): z = −x.
3) x /∈M , y /∈M : Ovde imamo dva sluqaja.
3.1) y − x /∈M : z = −x;
3.2) y − x ∈M : z = 1− x.
Posledica 68. Neka je R = R1 × · · · × Rn proizvod kvazilokalnih prstena
i x = (x1, . . . , xn), y = (y1, . . . , yn) ∈ R. Tada postoji z = (z1, . . . , zn) ∈ R
takav da je x+ z ∈ Id(R) i z + y ∈ U(R). Drugim reqima, CΓ(R) je povezan i
diam(CΓ(R)) = 2.
39
Dokaz: Direktna posledica teoreme 67.
Teorema 67 i njena posledica 68 daju nam mogunost za opis qis-
tog grafa xiroke klase poluperfektnih prstena. Komutativni polu-
perfektni prsteni su taqno oni prsteni koji su izomorfni direktnim
proizvodima kvazilokalnih prstena [34, teorema 23.11]. Klasi poluper-
fektnih prstena specijalno pripadaju Artinovi, dakle i svi konaqni
prsteni. Kod svih njih, qisti graf je dakle povezan i ima dijametar 2.
Istaknimo ovo u obliku sledee teoreme.
Teorema 69. Neka je R poluperfektan komutativan prsten. Tada je CΓ(R)
povezan i diam(CΓ(R)) = 2. Specijalno, ovo vai za Artinove, dakle i za
sve konaqne prstene.
Poluperfektni i qisti prsteni imaju zanimljivu vezu. Kamilo i
Ju [17, teorema 9], dali su sledeu karakterizaciju poluperfektnih
prstena: prsten je poluperfektan akko je qist i nema beskonaqan skup
ortogonalnih idempotenata. To znaqi da je diam(CΓ(R)) = 2, ako je R qist
prsten sa konaqno mnogo idempotenata. Ovaj rezultat moe se meutim
proxiriti na sve qiste, kao i na sve 2-dobre prstene. Da bi to dokazali,
potrebna nam je sledea lema.
Lema 70. Neka je R komutativan prsten koji zadovoljava uslov:
(γ) (∀x ∈ R)(∃y ∈ UI(R)) x+ y ∈ UI(R).
Tada je CΓ(R) povezan i diam(CΓ(R)) ≤ 2.
Dokaz: Neka su x, z ∈ R i x 6= z. Dokazujemo da je d(x, z) ≤ 2. Uslov (γ)
vai i za x− z; dakle postoji y ∈ UI(R) takav da je
(x− z) — y — 0
put u CΓ(R). Tada je:
x — (y − z) — z
traeni put.
40
Napomena 71. U lemi 70 vai i obratno. Ako je diam(CΓ(R)) ≤ 2, onda
je jasno da u prstenu R vai uslov (γ). Naime za x ∈ R je d(x, 0) ≤ 2, pa
mora postojati y ∈ UI(R) takav da je x+ y ∈ UI(R).
Teorema 72. Neka je R komutativan prsten. Tada je diam(CΓ(R)) ≤ 2 ako
je R qist ili 2-dobar prsten.
Dokaz: Samo treba proveriti da je ispunjen uslov (γ).
Ako je R qist i x ∈ R, onda x = e+ u, gde je e ∈ Id(R) i u ∈ U(R). Ako
odaberemo element y = −u, vidimo da je uslov (γ) zadovoljen.
Sliqno, ako je R 2-dobar i x ∈ R, imamo da je x = u + v, gde su
u, v ∈ U(R). Tada biramo y = −u.
Poznato je da klasa komutativnih qistih prstena sadri prstene di-
menzije 0, kvazilokalne prstene, kao i sve komutativne Fon Nojmanove
regularne prstene. Takoe znamo da su homomorfne slike i direktni
proizvodi qistih prstena qisti prsteni, kao i da je prsten formalnih
redova R[[X]] qist akko je R qist. Dokazi ovih tvrenja mogu se nai
u [4]. Vidimo da velika klasa komutativnih prstena ima povezan qisti
graf dijametra najvixe 2. Ostaje otvoren problem:
Da li postoji komutativan En-prsten R takav da je diam(CΓ(R)) > 2 ?
41
4.3 Rod qistog grafa
Ispitaemo najpre planarnost qistog grafa. Dokazaemo da je za
konaqan komutativan prsten sa jedinicom R graf CΓ(R) planaran akko
je |R| ≤ 4. U dokazu koristimo teoremu 1 i teoremu 4. Da bi uprostili
oznaqavanje ponekad emo pisati R = R1×· · ·×Rn umesto R ∼= R1×· · ·×Rn.
Teorema 73. Neka je R konaqan komutativan prsten sa jedinicom i neka
je |R| ≥ 5. Tada CΓ(R) nije planaran.
Dokaz: Kao xto smo napomenuli, R = R1×· · ·×Rn, gde je svaki Ri konaqan
lokalan prsten.
1) n ≥ 3: Uoqimo u grafu CΓ(R) podskup temena A = {a1, a2, a3}, gde
je a1 = (1, 1, 0, 0, . . . , 0), a2 = (0, 1, 1, 0, . . . , 0) i a3 = (1, 1, 1, 0, . . . , 0). Biramo
podskup temena B = {b1, b2, b3} na sledei naqin:
b1 = (0, 0, 0, 0, . . . , 0), b2 = (−1, 0, 0, 0, . . . , 0) i b3 = (0,−1, 0, 0, . . . , 0). Temena
iz B susedna su svakom temenu iz A, ako je char(R1) = 2. Ako char(R1) 6= 2,
teme b2 ne mora biti susedno sa a2, dok ostala temena ostaju susedna. U
tom sluqaju imamo put b2— c— a2, gde je c = (1, 0, 0, 0, . . . , 0), pa dobijamo
jednu potpodelu od K3,3. Dakle K3,3 ili neka njegova potpodela sadrana
je u CΓ(R), pa prema teoremi Kuratovskog on nije planaran.
2) R = R1 ×R2. Ovde imamo vixe mogunosti.
2.1) R = R1 × R2, gde je char(R1) 6= 2 i char(R2) 6= 2. Izborom pod-
skupova A = {(0, 0), (−1, 0), (0,−1)} i B = {(0, 1), (1, 0), (1, 1)} vidimo da je
K3,3 sadran u CΓ(R).
2.2) R = R1×R2, gde je jedan od prstena, na primer R1, karakteristike
2, dok drugi nije. Temena (0, 0), (0, 1), (1, 0) i (1, 1) qine kliku. Uoqimo
teme (1,−1). Ovo teme susedno je temenima (0, 0), (0, 1) i (1, 1), dok do
temena (1, 0) postoji put (1,−1)— (1, 2)— (0,−1)— (1, 0). Na taj naqin
dobijamo potpodelu grafa K5 sadranu u CΓ(R), pa on nije planaran.
2.3) R = R1 × R2, gde su oba prstena karakteristike 2. Zbog uslova
|R| ≥ 5 bar jedan od njih, na primer R2 ima vixe od 2 elementa. Neka jeM
42
maksimalan ideal u R2. Ako je M = {0}, onda je R2 polje karakteristike
2. Neka je a ∈ R2 \ {0, 1}. Podskupovi temena A = {(0, 0), (0, 1), (0, a)} i
B = {(1, 1), (1, a), (1, 0)} daju nam da je K3,3 sadran u CΓ(R). Neka je zato
M 6= {0} i x ∈M , x 6= 0. Element 1 + x je invertibilan u R2, pa je (1, 1 +
x) invertibilan u R. Dokazujemo da onda CΓ(R) sadri kao podgraf
potpodelu od K5 (Sl.2). Najpre, temena (0, 0), (0, 1), (1, 0), (1, 1) jasno
qine kliku. Teme (1, 1 + x) susedno je sa (0, 0) i imamo sledee puteve:
(1, 1+x)— (1, x)— (0, 1), (1, 1+x)— (0, 1+x)— (1, 0), (1, 1+x)— (0, x)— (1, 1).
3) n = 1: R je konaqan lokalan prsten sa maksimalnim idealom M .
Prema teoremi 3, konaqan komutativan prsten sa n pravih delitelja
nule ima najvixe (n + 1)2 elemenata, tj. |R| ≤ |Z(R)|2. Dakle, postoje
m1,m2 ∈ M , m1 6= 0 i m2 6= 0 (u suprotnom |R| ≤ 4). Podskupovi A =
{1, 1−m1, 1−m2} i B = {0,m1,m2} daju nam da je K3,3 ⊆ CΓ(R).
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯¯
½
½
½
½
½
½
½
½
½
½
½½
¡
¡
¡
¡
¡
¡
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
ZZL
L
L
L
L
L
L
L
L
L
L
L
L
LL
@
@
@
@
@
@
u u
u u
u
uu
u
(0, 0) (0, 1)
(1, 1) (1, 0)
(1, 1 + x)
(0, 1 + x)(0, x)
(1, x)
Slika 2
Lema 74. Neka su R1 i R2 komutativni prsteni. Ako je Km,n ⊆ CΓ(R1),
onda je Km,n ⊆ CΓ(R1 ×R2).
Dokaz: Neka je Km,n u CΓ(R1) odreen skupovima temena V1 = {a1, . . . , am}
i V2 = {b1, . . . , bn}. Tada je Km,n u CΓ(R1 × R2) odreen skupovima temena
W1 = {(a1, 1), . . . , (am, 1)} i W2 = {(b1, 0), . . . , (bn, 0)}.
43
Lema 75. Neka je R kvazilokalan komutativan prsten sa maksimalnim
idealom M . Tada je u CΓ(R) svaki element iz R \M susedan svakom ele-
mentu iz M . Elementi m1, m2 iz M susedni su akko je m1 +m2 = 0.
Dokaz: Ovo je oqigledno jer su 0 i 1 jedini idempotenti u kvazilokalnom
prstenu R.
Lema 76. Neka je R konaqan lokalan komutativan prsten sa maksimalnim
idealom M . Ako je |M | ≥ 5, onda je γ(CΓ(R)) ≥ 2. Ovo takoe vai i u
sluqaju |M | ≥ 3 i |U(R)| ≥ 7.
Dokaz: Moemo nai bar 5 razliqitih invertibilnih elemenata, jer za
svako a ∈ M vai 1 − a ∈ U(R). Svaki od njih je prema prethodnoj lemi
susedan svakom temenu iz M . Odavde je K5,5 ⊆ CΓ(R), pa je γ(CΓ(R)) ≥ 2,
prema tvrenju 5. Sliqno, u drugom sluqaju vai K3,7 ⊆ CΓ(R), pa je
γ(CΓ(R)) ≥ 2.
Lema 77. Neka je R komutativan prsten. Ako je |UI(R)| ≥ 8, onda je
γ(CΓ(R)) ≥ 2.
Dokaz: Neka su u1, . . . , u8 razliqita temena iz UI(R). Svako teme x susedno
je onda temenima ui − x, i = 1, . . . , 8. U najgorem sluqaju neki od ui, npr.
u1 jednak je 0 i 2x = 0. Onda je x susedan sa u2 − x, . . . , u8 − x. U svakom
sluqaju je dakle deg(x) ≥ 7. Tvrenje sledi primenom posledice 7.
Neka je R konaqan komutativan prsten sa jedinicom i R = R1×· · ·×Rn
njegova reprezentacija, gde su Ri konaqni lokalni prsteni.
Teorema 78. Neka je R konaqan komutativan prsten sa jedinicom. Ako je
R = R1 × · · · × Rn i n ≥ 3, onda je γ(CΓ(R)) ≥ 2.
Dokaz: Dovoljno je dokazati za sluqaj n = 3. Dokaz je meutim direktna
posledica leme 77, jer prsten R = R1 ×R2 ×R3 ima bar 8 idempotenata.
44
Dovoljno je dakle razmotriti sluqajeve n = 1 i n = 2. Neka je najpre
n = 1, tj. R je konaqan lokalan prsten sa maksimalnim idealom M .
Poznato je da je u tom sluqaju |R| = pk, za neki prost p i pozitivan k,
kao i da |M | deli |R| (tvrenje 2).
Teorema 79. Neka je R konaqan lokalan komutativan prsten. Tada je
γ(CΓ(R)) = 1 akko je R izomorfan jednom od sledeih prstena: F5, F7, Z8,
F2[X]/(X3), F2[X, Y ]/(X,Y )2, Z4[X]/(2X,X2) ili Z4[X]/(2X,X2 − 2).
Dokaz: Neka je najpre k = 1 (u gore spomenutoj notaciji), tj. |R| = p.
Tada je R ∼= Fp. Za p > 7, γ(CΓ(R)) ≥ 2 prema lemi 77, dok su CΓ(F2) i
CΓ(F3) oqigledno planarni. Kako je CΓ(F5) = K5 i CΓ(F7) = K7 to su i
jedini qisti grafovi roda 1 u ovom sluqaju.
Neka je sada k = 2, tj. |R| = p2. Prema [19], jedine mogunosti za R su
Fp2, Fp[X]/(X2) ili Zp2. Dokaimo da qisti grafovi ovih prstena nisu
toroidalni. Ako je R = Fp2 i p > 2, onda γ(CΓ(R)) ≥ 2 prema lemi 77. Za
R = F22, γ(CΓ(R)) = 0. Ako je R = Fp[X]/(X2), onda je |M | = p, pa za p ≥ 5
prema lemi 76, γ(CΓ(R)) ≥ 2. Kako je CΓ(F2[X]/(X2)) planaran, ostaje
jedino sluqaj R = F3[X]/(X2). Jednostavnom proverom vidimo da je ovde
δ(CΓ(R)) = 6, kao i da je deg(X) = 7. Prema posledici 7, CΓ(R) nije
roda 1. Sluqaj R = Zp2 sliqan je prethodnom; naime i ovde je |M | = p i
CΓ(Z22) je planaran. Ostaje jedino sluqaj R = Z32. Ovde je δ(CΓ(R)) = 6
i deg(3) = 7. Dakle, meu lokalnim prstenima kardinalnosti p2, nema
onih koji imaju toroidalan qisti graf.
Razmotrimo sluqaj k = 3, |R| = p3. Kako je CΓ(F23) = K8, on je roda
2. Qisti grafovi ostalih konaqnih polja Fp3, za p ≥ 3, oqigledno nisu
roda 1 prema lemi 77. Dalje, ako R nije polje, onda M ima bar p eleme-
nata. Ako je p ≥ 3, onda budui da ima dovoljno invertibilnih eleme-
nata, γ(CΓ(R)) ≥ 2, prema lemi 76. Ostaje dakle da razmotrimo sluqaj
|R| = 23, gde R nije polje. Prema [19, strana 687] mogunosti su: Z23,
F2[X]/(X3), F2[X, Y ]/(X,Y )2, Z4[X]/(2X,X2) ili Z4[X]/(2X,X2− 2). Direk-
tnom proverom vidimo da su qisti grafovi prva tri prstena izomorfni
45
sa K4,4, dakle toroidalni, kao i da su qisti grafovi preostala dva
prstena izomorfni i da se mogu utopiti u torus (Sl.3). Dakle, svi su
roda 1.
U sluqaju |R| = pk, k ≥ 4 lako se vidi da nema toroidalnih grafova.
´
´
´
´
³³
³³
PPPP
Q
Q
Q
Q´
´
´
´
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
´
´
´
´
³³
³³
Q
Q
Q
Q
´
´
´
´
PPPP
s s s s
s s s
s
s
s
s
s s s
0 0
0 0
2 X
2 X
2 +X 2 +X
3
1
3 +X
1 +X
´
´
´
´QQ
Q
Q
¡
¡
¡
@
@
@¢
¢
¢S
S
S
S
S
S
Q
Q
Q
Q
s s s
s s
s
s
s
s
s
s
ss
s s
(0, 0) (0, 0)
(0, 0) (0, 0)
(1, 0) (1, 0)
(0, 1) (0, 1)
(0, X)
(0, X)
(1, X)
(1, X)
(1, 1)
(1, 1 +X) (0, 1 +X)
Sl.3. CΓ(Z4[X]/(2X,X2)) Sl.4. CΓ(F2 × F2[X]/(X2))
Teorema 80. Neka je R = R1 × R2 proizvod konaqnih lokalnih komuta-
tivnih prstena sa jedinicom. Neka bar jedan od prstena R1, R2 ima vixe
od 4 elementa. Tada je γ(CΓ(R1 ×R2)) ≥ 2.
Dokaz: Pretpostavimo da je |R2| ≥ 5.
Ako je R2 polje i 1, a, b, c njegovi razliqiti invertibilni elementi,
onda CΓ(R) sadri K4,5 kao podgraf, pa je γ(CΓ(R)) ≥ 2. To se moe
videti npr. ako uoqimo podskupove temena V1 = {(1, 1), (1, a), (1, b), (1, c)} i
V2 = {(0, 0), (0, 1), (0, a), (0, b), (0, c)}.
Ako R2 nije polje, onda je |R2| = pn i |M | ≥ p. Neka je najpre |p| ≥ 5
i neka su 0, a, b, c, d razliqiti elementi iz M . Za izbor podskupova
V1 = {0, a, b, c} i V2 = {1, 1−a, 1− b, 1− c, 1−d} dobijamo da je K4,5 ⊆ CΓ(R2).
Prema lemi 74, bie i K4,5 ⊆ CΓ(R1×R2), pa je γ(CΓ(R)) ≥ 2. Ostaju nam
dakle jedino sluqajevi p = 2 i p = 3.
Neka je p = 3, |R2| = 3n i |M | ≥ 3. Ovde je dovoljno razmotriti
minimalan sluqaj, M = {0, a,−a}. Neka je V1 = {(0, 0), (0, a), (0,−a)} i
V2 = {(1, 1+ a), (1, 1− a), (1,−1− a), (1, a− 1), (1, 1), (1,−1), (1, 0)}. Sva temena
46
skupa V2 susedna su temenima skupa V1, osim temena (1, 0) koje nije susedno
sa (0, a) i (0,−a). Teme (1, 0) spojeno je sa (0, a) preko temena (0, 1−a), dok
je sa (0,−a) spojeno preko (0, 1 + a). Tako dobijamo da je potpodela od
K3,7 sadrana u CΓ(R), pa on u ovom sluqaju ne moe biti roda 1.
Ostaje nam sluqaj |R2| = 2n. Oqigledno γ(CΓ(R1×R2)) ≥ 2, za n ≥ 4. Za
n = 3, mogunosti za R2 prema [19], su: Z23, F2[X]/(X3), F2[X, Y ]/(X, Y )2,
Z4[X]/(2X,X2) ili Z4[X]/(2X,X2 − 2). U svim sluqajevima je |M | = 4.
Neka je zato M = {0, a, b, a+ b}.
Ako char(R1) 6= 2, izborom temena V1 = {(0, a), (0, b), (0, a + b)} i V2 =
{(−1, 1−a), (−1, 1− b), (1, 1−a), (1, 1− b), (1, 1), (−1, 1), (1, 1−a− b)}, dobijamo
da je K3,7 ⊆ CΓ(R1 ×R2).
Ako je char(R1) = 2, biramo V1 = {(1, 1− a), (1, 1− b), (1, 1− a− b), (1, 1)} i
V2 = {(0, 0), (0, a), (0, b), (0, a+ b), (0, 1)} (Sl.5). Sva temena skupa V2 susedna
su temenima iz V1, osim temena (0, 1). Teme (0, 1) povezano je meutim
sa ostalim temenima iz V1 na sledei naqin: sa temenom (1, 1− a) preko
(1, a); sa (1, 1− b) preko (1, b); sa (1, 1− a− b) preko (1, a+ b); sa (1, 1) preko
(1, 0). Na taj naqin dobijamo potpodelu od K4,5 sadranu u CΓ(R), pa je
i ovde γ(CΓ(R1 ×R2)) ≥ 2.
¡
¡
¡
¡
¡
¡
¡
¡¡
©©
©©
©©
©©
©©
©©
©©
©©
©
³³
³³
³³
³³
³³
³³
³³
³³
³³
³³
³³
³³
³³
@
@
@
@
@
@
@
@@
¡
¡
¡
¡
¡
¡
¡
¡¡
©©
©©
©©
©©
©©
©©
©©
©©
©
HH
HH
HH
HH
HH
HH
HH
HH
H
@
@
@
@
@
@
@
@@
¡
¡
¡
¡
¡
¡
¡
¡¡
PP
PP
PP
PP
PP
PP
PP
PP
PP
PP
PP
PP
PP
HH
HH
HH
HH
HH
HH
HH
HH
H
@
@
@
@
@
@
@
@@
XXX
XXX
XXX
XXX
XXX
XXX
XXX
XXX
XXX
XXX
XXX
X
PP
PP
PP
PP
PP
PP
PP
PP
PP
PP
PP
PP
PP
HH
HH
HH
HH
HH
HH
HH
HH
H
@
@
@
@
@
@
@
@@
u u u u u
u u u u
u
u
uu
(0, 0) (0, a) (0, b) (0, a+ b) (0, 1)
(1, 1− a) (1, 1− b) (1, 1) (1, 1− a− b)
(1, a) (1, b)
(1, 0)
(1, a+ b)
Slika 5
Teorema 81. Neka je R = R1 × R2, gde su R1 i R2 konaqni lokalni komu-
tativni prsteni sa jedinicom. Tada je γ(CΓ(R)) = 1 akko je R izomorfan
jednom od sledeih prstena: F2 × F3, F2 × Z4, F2 × F4 ili F2 × F2[X]/(X2).
Dokaz: Prema teoremi 80 dovoljno je posmatrati qiste grafove sledeih
47
prstena: F2 × F2, F2 × F3, F2 × Z4, F2 × F4, F2 × F2[X]/(X2), F3 × F3, F3 × F4,
F3×Z4, F3×F2[X]/(X2), F4×Z4, F4×F4, F4×F2[X]/(X2), Z4×Z4, Z4×F2[X]/(X2)
ili F2[X]/(X2)× F2[X]/(X2).
Ako je R jedan od prstena F3 × F4, F4 × Z4, F4 × F4 ili F4 × F2[X]/(X2),
onda je γ(CΓ(R)) ≥ 2 prema lemi 77, jer se direktnom proverom vidi da
je u svakom od ovih prstena |UI(R)| = 9.
Ako je R jedan od prstena F3 × F3, F3 ×Z4, F3 × F2[X]/(X2), Z4 ×Z4 ili
Z4 × F2[X]/(X2), onda je γ(CΓ(R)) ≥ 2 prema posledici 7, jer u svakom
od ovih prstena vai δ(CΓ(R)) = 6 i svaki od njih ima bar jedno teme
stepena 7. U F3 × F3 i F3 × Z4 je npr. deg(0, 1) = 7; u F3 × F2[X]/(X2),
deg(1, x) = 7; u Z4 × Z4, deg(0, 3) = 7; dok je u Z4 × F2[X]/(X2) deg(1, 0) = 7.
Za prsten R = F2[X]/(X2)×F2[X]/(X2) takoe je δ(CΓ(R)) = 6, ali ovde
svako teme ima stepen 6. Prema posledici 7, γ(CΓ(R)) = 1 akko je CΓ(R)
1-skeleton 6-regularne triangulacije torusa. U ovom sluqaju nemamo
traenu triangulaciju: na primer temena (0, x) i (1, 1) su susedna, ali
ivica koja ih spaja nije stranica nijednog trougla jer u CΓ(R) ne postoji
teme susedno sa oba.
Q
Q
Q
Q
©©
©©
©©
´
´
´
´
³³
³³
³³
³³³
¢
¢
¢aaaaaaa
©©
©
HHH
¡
¡
¡
³³
³³
PPPP
s s s s
s s ss
s s s
s s s s
(0, 0) (0, 0)
(0, 0) (0, 0)
(1, a)
(1, 1)
(1, a)
(1, 1)
(0, 1) (1, 0)
(0, 1) (1, 0)
(0, 1 + a)
(1, 1 + a)
(0, a)
¡
¡
¡
¡
³³
³³HHH
Z
Z
Z
Z
ZZ
­
­
­
­­
#
#
#
#
#
#
#
¡
¡
¡
!!
!!
!!
! A
A
A
A
A
A
s s s s s
s s s
s
s
s
s s s s
s
(0, 1) (0, 1)
(0, 1) (0, 1)
(1, 0) (1, 0)
(0, 0) (0, 0)
(1, 3)
(1, 3)
(1, 1)
(1, 1)
(0, 3)
(0, 3)
(1, 2)
(0, 2)
Slika 6. CΓ(F2 × F4) Slika 7. CΓ(F2 × Z4)
Zbog kardinalnosti skupa temena, γ(CΓ(F2×F2)) = 0 i γ(CΓ(F2×F3)) = 1.
Konaqno, qisti grafovi prstena F2×F2[X]/(X2), F2×F4 i F2×Z4 mogu se
utopiti u torus (slike 4, 6 i 7).
48
GLAVA 5
LINIJSKI GRAF TOTALNOG GRAFA
U teoriji grafova grafu G pridruuje se njegov linijski graf L(G),
tako xto se za temena grafa L(G) uzimaju sve ivice grafa G. Dva temena
u L(G) su susedna akko odgovarajue ivice u G imaju zajedniqko teme.
Tako definisan graf omoguava nam da osobine grafa Γ koje zavise samo
od njegovih ivica razmatratamo kao osobine grafa L(G) koje zavise od
njegovih temena. Ova osobina veoma je korisna za razne probleme u
teoriji grafova. Na primer, za graf G = (V,E), uparenje (matching) u
G je podskup skupa ivica takav da nikoje dve ivice nemaju zajedniqko
teme. Uparenju odgovara nezavisan skup (podskup skupa temena takvih
da nikoja dva nisu susedna) u L(G). Jednu od najstarijih i najvani-
jih teorema o linijskim grafovima dokazao je Vitni (1932). On je u
[53] dokazao da se povezan graf G moe potpuno rekonstruisati iz nje-
govog linijskog grafa L(G), osim u sluqaju L(G) = K3. U radu [30],
autori istrauju utapanja linijskog grafa L(Γ(R)) i klasifikuju do na
izomorfizam sve konaqne komutativne prstene qiji su linijski grafovi
grafova delitelja nule planarni ili toroidalni.
Motivisani ovim rezultatima i poznajui strukturu totalnog grafa
TΓ(R), prirodno je postaviti pitanje strukture njegovog linijskog grafa
i istraiti veze meu njima. Ovde emo istraiti neke od osobina ovog
grafa. Pokazaemo kada je Ojlerov i koliki je njegov obim. Glavni
rezultati vezani su za problem utapanja linijskog grafa. Daemo, do
na izomorfizam, listu svih konaqnih komutativnih prstena za koje je
linijski graf totalnog grafa planaran ili toroidalan. Zanimljivo je
da se lista konaqnih prstena za koje je totalni graf planaran ([36]),
poklapa sa listom konaqnih prstena za koji je asocirani linijski graf
planaran, dok za toroidalne to ne vai. Dokazaemo takoe da za dati
ceo broj g ≥ 0, postoji samo konaqno mnogo klasa izomorfnih konaqnih
prstena qiji linijski graf (totalnog grafa) ima rod g.
5.1 Struktura i osobine grafa L(TΓ(R))
Neka je R komutativan prsten sa jedinicom, TΓ(R) njegov totalni graf
i L(TΓ(R)) njegov linijski graf. Ako za elemente x, y ∈ R vai x + y ∈
Z(R), onda je {x, y} teme grafa L(TΓ(R)). Za ovo teme koristimo oznaku
[x, y]. Iz definicije grafa TΓ(R) neposredno sledi da stepen svakog
temena zavisi od broja delitelja nule, kao i od toga da li je 2 ∈ Z(R).
Lako se moe pokazati ([36, lema 1.1]) da vai sledee tvrenje.
Lema 82. Neka je R konaqan komutativan prsten sa jedinicom i neka je
x teme grafa TΓ(R). Tada je
deg(x) =
 |Z(R)| − 1 ako 2 ∈ Z(R) ili x ∈ Z(R),|Z(R)| inaqe.
Teorema 83.
gr(L(TΓ(R))) =

3 ako je |Z(R)| ≥ 3 i R  Z2 × Z2,
4 ako je R ∼= Z2 × Z2,
∞ ako je |Z(R)| ≤ 2.
Dokaz:
50
1. |Z(R)| = 1: Ako R nema pravih delitelja nule mogua su dva sluqaja.
Ako char(R) = 2, onda je L(TΓ(R))= ∅, jer je TΓ(R) totalno nepovezan.
Ako char(R) 6= 2, onda je TΓ(R) disjunktna unija |R|/2 grafova K2 i
izolovanog temena 0. Tada je L(TΓ(R)) totalno nepovezan graf sa
|R|/2 temena. Dakle, gr(L(TΓ(R))) =∞.
2. |Z(R)| = 2: Poznato je ([8]) da postoje samo dva neizomorfna komu-
tativna prstena sa jednim pravim deliteljem nule: Z4 i Z2[X]/(X2).
Oni imaju izomorfne totalne grafove – disjunktne unije dva kom-
pletna grafa K2. Odavde vidimo da je L(TΓ(R)) unija dva izolovana
temena, pa je i ovde gr(L(TΓ(R))) =∞.
3. |Z(R)| ≥ 3:
3.1) Neka je Z(R) ideal i x, y ∈ Z∗(R), x 6= y. Onda TΓ(R) sadri
trougao 0— x— y— 0. Odavde je [0, x]— [x, y]— [y, 0]— [0, x] trougao
u L(TΓ(R)), tj. gr(L(TΓ(R))) = 3.
3.2) Neka Z(R) nije ideal u R. Onda postoje x, y ∈ Z∗(R) takvi da
x + y ∈ Reg(R). Ako je pri tom |Z(R)| > 3, tj. ako postoji z ∈
Z∗(R) razliqit od x i y, onda u TΓ(R) postoji zvezda podgraf K1,3
(teme 0 susedno je temenima x, y i z). Kako je L(K1,3) = C3, to
je [0, x]— [0, y]— [0, z]— [0, x] trougao u L(TΓ(R)) i gr(L(TΓ(R))) = 3.
Ostaje samo da ispitamo sluqaj |Z(R)| = 3. Prema [8] postoje tri
neizomorfna komutativna prstena sa tri delitelja nule: Z3[x]/(x2),
Z9 i Z2 × Z2. Prva dva prstena otpadaju, jer je Z(R) ideal, dok je
TΓ(Z2×Z2) = C4. Kako je L(C4) = C4, to je gr(L(TΓ(Z2×Z2))) = 4.
Neka je R konaqan komutativan prsten sa jedinicom. Ako je R = Z2,
onda je L(TΓ(R)) = ∅. Ako je R = Fq polje sa q ≥ 3 elemenata, onda je
L(TΓ(R)) totalno nepovezan graf sa (q − 1)/2 temena. U tom sluqaju je
deg([u, v]) = 0 za svako teme [u, v] iz L(TΓ(R)), pa je δ(L(TΓ(R))) = 0. Da bi
izbegli trivijalne sluqajeve nadalje emo obiqno pretpostavljati da R
nije polje, tj. da je |Z(R)| ≥ 2.
51
Teorema 84. Neka je R konaqan komutativan prsten koji nije polje. Tada
je L(TΓ(R)) regularan akko 2 ∈ Z(R). Stepen regularnosti tada je jednak
2|Z(R)| − 4. Ako sa |V | i |E| oznaqimo broj temena i ivica L(TΓ(R)), onda
je:
|V | = |R|(|Z(R)| − 1)
2
, |E| = |R|(|Z(R)| − 1)(|Z(R)| − 2)
2
.
Dokaz: Neka je najpre 2 ∈ Z(R). Tada je prema lemi 82, TΓ(R) regularan
graf stepena |Z(R)|−1 sa |R|(|Z(R)|−1)/2 ivica. Neka je [u, v] proizvoljno
teme linijskog grafa. Tada je
deg([u, v]) = deg(u) + deg(v)− 2 = 2|Z(R)| − 4,
odakle sledi traeno tvrenje.
Neka sada 2 /∈ Z(R). Kako R nije polje, postoji x ∈ Z(R), x 6= 0. Takoe
iz pretpostavki je 1 6= −1. Tada
deg([0, x]) = 2|Z(R)| − 4 6= deg([1,−1]) = 2|Z(R)| − 2,
pa L(TΓ(R)) nije regularan.
Teorema 85. Neka je R konaqan komutativan prsten koji nije polje. Tada
je
δ(L(TΓ(R))) = 2|Z(R)| − 4.
Dokaz: Neka je [u, v] teme grafa L(TΓ(R)). Prema lemi 82, deg([u, v]) je
2|Z(R)| − 2, 2|Z(R)| − 3 ili 2|Z(R)| − 4. Dovoljno je pokazati da bar jedno
teme grafa L(TΓ(R)) ima stepen 2|Z(R)| − 4. Moemo na primer uzeti
teme [0, x], gde x ∈ Z∗(R).
Ispitaemo sada uslove pod kojima je L(TΓ(R)) Ojlerov. Moemo
se ograniqiti na sluqaj kada je R konaqan prsten koji nije lokalan
(ako je R beskonaqan nema smisla traiti Ojlerovu konturu, a ako je
R konaqan i lokalan, onda je Z(R) = M njegov maksimalan ideal, pa je
TΓ(R) nepovezan). Moe se dakle pretpostaviti da je R ∼= R1 × · · · × Rn,
52
gde su Ri konaqni lokalni prsteni i n ≥ 2. Kao xto ve znamo, za takav
prsten R vai diam(TΓ(R)) = 2.
Teorema 86. Neka je R konaqan komutativan prsten koji nije lokalan.
Tada je L(TΓ(R)) Ojlerov akko 2 ∈ Z(R).
Dokaz: Pretpostavimo da R zadovoljava uslove teoreme i da 2 ∈ Z(R).
Tada prema lemi 82, svako teme grafa TΓ(R) ima stepen |Z(R)| − 1, tj.
TΓ(R) je regularan stepena |Z(R)| − 1. Neka je [x, y] proizvoljno teme
linijskog grafa L(TΓ(R)). Tada je
deg([x, y]) = deg(x) + deg(y)− 2 = 2|Z(R)| − 4
paran, pa je L(TΓ(R)) Ojlerov.
Neka sada 2 /∈ Z(R). Prema datim uslovima Z(R) nije ideal, pa pos-
toje x, y ∈ Z(R) takvi da x + y /∈ Z(R). Tada su temena −x ∈ Z(R) i
x + y ∈ Reg(R) susedna u TΓ(R). Prema lemi 82, deg(−x) = |Z(R)| − 1 i
deg(x + y) = |Z(R)|. Uoqimo teme [−x, x + y] u linijskom grafu L(TΓ(R)).
Tada je
deg([−x, x+ y]) = deg(−x) + deg(x+ y)− 2 = 2|Z(R)| − 3.
Linijski graf L(TΓ(R)) sadri teme neparnog stepena pa nije Ojlerov.
Napomena 87. Uslov 2 ∈ Z(R) moe se zameniti uslovom R ∼= R1×· · ·×Rn
i 2 je delitelj nule u bar jednom Ri, tj. bar jedan od njih ima Z2 kao
polje ostataka.
5.2 Utapanja L(TΓ(R))
Pri ispitivanju roda nekog grafa bitnu ulogu imaju njegovi kom-
pletni i kompletno bipartitni podgrafovi. Ovo smo ve videli kod
53
ispitivanja roda qistog grafa a isto e vaiti i za rod linijskog
grafa. Podsetimo se da prema jednakostima 1.1.2 i 1.1.3 vai:
γ(Kn) = 0, za n = 1, 2, 3, 4,
γ(Kn) = 1, za n = 5, 6, 7,
γ(Kn) ≥ 2, za n ≥ 8,
γ(Km,1) = γ(Km,2) = 0, za svako m,
γ(Km,3) = γ(K4,4) = 1, za 3 ≤ m ≤ 6,
γ(Km,n) ≥ 2, inaqe.
Rod grafova L(Kn) i L(Km,n) razmatran je u radu [30]. Mada za nji-
hov rod nemamo eksplicitnu formulu (kao u tvrenju 5), date su neke
korisne procene i odreen je njihov rod u nekim specijalnim sluqaje-
vima. Autori su izmeu ostalog dokazali da je γ(L(K2,n)) ≥ 2, za n ≥ 5 i
γ(L(K3,n)) ≥ 2, za n ≥ 4. Ovde neemo detaljno navoditi sve procene, ve
emo se po potrebi pozvati na neke od tih postojeih rezultata.
Lema 88. Neka je R konaqan komutativan prsten takav da je |Z(R)| ≥ 5.
Tada je γ(L(TΓ(R))) ≥ 1.
Dokaz: Prema posledici 7 i teoremi 85, vai
δ(L(TΓ(R))) = 2|Z(R)| − 4 ≥ 6.
Odavde sledi traeni rezultat.
Prema lemi 88, pri ispitivanju planarnosti grafa L(TΓ(R)) moemo
se ograniqiti na prstene sa malim brojem delitelja nule. Ispitaemo
najpre nelokalan sluqaj.
Teorema 89. Neka je R konaqan komutativan prsten koji nije lokalan.
Tada je L(TΓ(R)) planaran akko je R ∼= Z2 × Z2 ili R ∼= Z2 × Z3.
Dokaz: Moemo pretpostaviti da je R ∼= R1 × R2 × · · · × Rn, gde je n ≥ 2,
svaki Ri je lokalan prsten i |R1| ≤ |R2| ≤ · · · ≤ |Rn|.
54
1) n ≥ 3: Tada je |Z(R)| ≥ 7, pa L(TΓ(R)) ne moe biti planaran prema
lemi 88 (minimalan takav Z2 × Z2 × Z2 ima 7 delitelja nule).
2) R ∼= R1 × R2 i za bar jedan od njih, na primer za R2, vai |R2| ≥ 5.
Tada γ(L(TΓ(R))) ≥ 1 prema lemi 88, jer (0, a1), . . . , (0, a5) ∈ Z(R), ai ∈ R2.
3) R ∼= R1 ×R2 i |R1|, |R2| ≤ 4. Ispitajmo sve mogunosti.
3.1) R ∼= Z2 × Z2. Tada je L(TΓ(R)) = C4 oqigledno planaran.
3.2) R ∼= Z2×Z3 ∼= Z6. Tada je L(TΓ(R)) takoe planaran (slike 8 i 9).
½
½
½
½
½
½
½
½
½
½
½½J
J
J
J
J
J
J
J
J
J
J
J
s s
s s
s
s
0 3
4 5
2
1
[4, 5]
[2, 4]
[0, 4]
[0, 2]
[0, 3]
[3, 5]
[1, 3]
[1, 5]
[1, 2]
````
````
````
`¡`
¡
¡
@
@
@
¡
¡
¡
ÃÃÃÃ
ÃÃÃÃ
ÃÃÃÃ
ÃÃ
@
@
@
@
@
@
@
@@
³³
³³
³³
³³³
HH
HH
HH
£
£
£
£
£
£
£
££
s
s
s
s
s
s
s
s
s
Slika 8. TΓ(Z2 × Z3) Slika 9. L(TΓ(Z2 × Z3))
3.3) |R1| = 2, |R2| = 4. Mogunosti su: Z2×F4, Z2×Z4 i Z2×Z2[X]/(X2).
Sluqaj Z2 × F4 posebno je razmotren u teoremi 92, gde je dokazano da
L(TΓ(Z2 × F4)) nije ni toroidalan. Lako je proveriti da ostala dva
prstena imaju 6 delitelja nule, pa ni njihovi linijski grafovi nisu
planarni prema lemi 88.
3.4) R ∼= Z3 × Z3. Ovde je |Z(R)| = 5, pa L(TΓ(R)) nije planaran prema
lemi 88.
3.5) U preostalim sluqajevima oqigledno je |Z(R)| ≥ 7, pa L(TΓ(R))
nije planaran prema lemi 88.
Dalje razmatramo lokalan sluqaj. Neka je R konaqan lokalan prsten
sa maksimalnim idealom M 6= {0}. Tada je Z(R) = M , pa delitelji nule
formiraju ideal. Dakle TΓ(R) je nepovezan i struktura mu je poznata
prema teoremi 8:
1) Ako 2 ∈ Z(R), onda je TΓ(R) disjunktna unija |R/M | kopija K |M |.
55
2) Ako 2 /∈ Z(R), onda je TΓ(R) disjunktna unija kompletnog grafa
K |M | i (|R/M | − 1)/2 kompletno bipartitnih grafova K|M |,|M |.
Osim ove teoreme u dokazu koristimo i poznate rezultate: Ako je
R konaqan lokalan prsten sa maksimalnim idealom M , onda je |R| = pk
i |M | | |R| (tvrenje 2). Koristimo listu konaqnih prstena do reda p5
([19, 20]) i teoremu 3.
Teorema 90. Neka je R konaqan lokalan komutativan prsten sa jedini-
com koji nije polje. Tada je L(TΓ(R)) planaran akko je R izomorfan jed-
nom od sledeih prstena: Z4, Z2[X]/(X2), Z8, Z2[X]/(X3), Z2[X,Y ]/(X, Y )2,
Z4[X]/(2X,X2), Z4[X]/(2X,X2 − 2), F4[X]/(X2) ili Z4[X]/(X2 +X + 1).
Dokaz: Neka je |R| = pk. Primetimo najpre da je dovoljno razmotriti
sluqajeve p ∈ {2, 3}. Naime, ako je p ≥ 5, onda s obzirom da R nije
polje i da |M | | pk, mora da vai |Z(R)| = |M | ≥ 5. Prema lemi 88,
γ(L(TΓ(R))) ≥ 1.
1) k = 2. Mogunosti su: Fp[X]/(X2) i Zp2.
Ako je R = F2[X]/(X2) ili R = Z22, onda je L(TΓ(R)) trivijalno pla-
naran (ima 2 temena). Ako je R = F3[X]/(X2) ili R = Z32, onda 2 /∈ Z(R),
pa je TΓ(R) = K3∪K3,3. Moe se pokazati (videti [30]) da je γ(L(K3,3)) = 1,
pa ovi linijski grafovi nisu planarni.
2) k = 3. Ako je p = 3 (tj. |R| = 27), onda 2 /∈ Z(R); odavde je K3,3 ⊆
TΓ(R). Dakle L(TΓ(R)) nije planaran pa je dovoljno razmotriti sluqaj
p = 2. Kako R nije polje mogunosti su: Z23, Z2[X]/(X3), Z2[X, Y ]/(X, Y )2,
Z4[X]/(2X,X2) ili Z4[X]/(2X,X2−2). Lako je videti da svi prsteni imaju
izomorfne totalne grafove, disjunktne unije dva kompletna grafa K4.
Kako je γ(L(K4)) = 0 (moe se videti direktnim crtanjem u ravni), sledi
da su odgovarajui linijski grafovi planarni.
3) k = 4. Posmatramo sada lokalne prstene reda p4. Dovoljno je
razmotriti sluqaj p = 2, iz istog razloga kao i za k = 3. Dakle |R| =
16 i |M | | 16. Sluqaj |M | = 1 otpada jer R nije polje. Sluqaj |M | =
56
2 otpada jer dovodi do kontradikcije, 16 = |R| ≤ |Z(R)|2 = |M |2 = 4.
Sluqaj |M | = 8 otpada jer onda ima previxe delitelja nule, pa prema
lemi 88, linijski graf nije planaran. Ostaje dakle samo sluqaj |M | =
4. Postoji taqno 21 neizomorfnih lokalnih komutativnih prstena sa
jedinicom reda 16 ([20]). Od svih njih samo 2 zadovoljavaju uslov |M | = 4:
F4[X]/(X2) i Z4[X]/(X2 + X + 1). Oni imaju izomorfne totalne grafove
– disjunktne unije 4 kompletna grafa K4. Kako je L(K4) planaran, kao
i u prethodnom sluqaju dolazimo do zakljuqka da je za ova dva prstena
L(TΓ(R)) planaran.
4) k ≥ 5. I ovde se moemo ograniqiti na sluqaj p = 2, |R| = 2k.
Sluqaj |M | = 4 tada nije mogu, jer je |R| ≤ |M |2. U svim ostalim
sluqajevima ima previxe delitelja nule, pa prema lemi 88 oni nisu
planarni.
Lista konaqnih komutativnih prstena sa jedinicom za koje je L(TΓ(R))
planaran:
Z2 × Z2, Z2 × Z3, Z4, Z2[X]/(X2), Z8, Z2[X]/(X3), Z2[X,Y ]/(X,Y )2,
Z4[X]/(2X,X2), Z4[X]/(2X,X2 − 2), F4[X]/(X2), Z4[X]/(X2 +X + 1).
Lema 91. Neka je R konaqan komutativan prsten. Vai:
|Z(R)| > 5 =⇒ γ(L(TΓ(R))) > 1.
Dokaz: Primenom teoreme 85, vidimo da je δ(L(TΓ(R))) = 2|Z(R)| − 4 > 6.
Tada je prema tvrenju 6, γ(L(TΓ(R))) > 1.
Teorema 92. Neka je R konaqan komutativan prsten sa jedinicom koji
nije lokalan. Tada je γ(L(TΓ(R))) 6= 1.
Dokaz: Prema lemi 91 dovoljno je ograniqiti se na razlaganje R ∼= R1 ×
R2, gde je |R1| ≤ |R2|. Dokaz izvodimo diskusijom kardinalnosti prstena
R2.
1) |R2| ≥ 5. Tada je |Z(R)| ≥ 6, pa je γ(L(TΓ(R))) > 1 prema lemi 91.
57
2) |R2| = 4. Ovde imamo 2 mogunosti.
2.1) |Z(R2)| = 2. Tada |Z(R)| = 6, pa je γ(L(TΓ(R))) > 1 prema lemi 91.
2.2) |Z(R2)| = 1. Tada je R2 ∼= F4. Razmatramo minimalan sluqaj
R ∼= Z2 × F4. Imamo da je δ(TΓ(R)) = 4, pa je δ(L(TΓ(R))) = 6. Primen-
jujui tvrenje 6 vidimo da je γ(L(TΓ(R))) = 1 akko je taj graf regu-
larna triangulacija torusa. Dokaimo da ovaj graf ne ostvaruje tri-
angulaciju torusa. Neka je R = Z2 × F4, F4 = Z2[X]/(X2 + X + 1) i x
odgovarajua klasa. Tada je Z(R) = {v1, v2, v3, v4, v5} i Reg(R) = {v6, v7, v8},
gde je v1 = (0, 0), v2 = (0, x), v3 = (0, x + 1), v4 = (0, 1), v5 = (1, 0), v6 = (1, x),
v7 = (1, x+ 1) i v8 = (1, 1).
Graf TΓ(R) je regularan graf stepena 4 sa 8 temena i 16 ivica, pa je
L(TΓ(R)) regularan stepena 6 sa 16 temena i 48 ivica (linijski graf reg-
ularnog grafa stepena r sa n temena je takoe regularan stepena 2r−2 sa
nr/2 temena i nr(r−1)/2 ivica). Radi lakxeg zapisa oznaqimo teme [vi, vj]
grafa L(TΓ(R)) sa wi,j. Graf L(TΓ(Z2×F4)) ima 16 temena: w1,2, w1,3, w1,7,
w1,8, w2,3, w2,5, w2,7, w3,4, w3,7, w4,5, w4,6, w4,8, w5,6, w5,8, w6,7 i w6,8. Temena
wi,j i wk,l su susedna akko {i, j} ∩ {k, l} 6= ∅, pa je broj ivica 48. Po broju
temena, ivica i pljosni (Ojlerova teorema), L(TΓ(Z2×F4)) triangulixe
torus. Svako teme grafa dakle mora biti centar nekog xestougla (ste-
pen svih temena je 6). Kako su temena ravnopravna, dokazujemo da tako
nexto nije mogue, na primer za teme w1,2.
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
¢
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
As
s
s
s
s
s
s s
s
s
s
s
s
s s
s
s
s
s
s
s
w1,2 w1,2 w1,2
w2,5 w2,7 w2,5 w2,3
w2,7
w2,5
w2,7w1,3
a) b) v)Slika 10.
Pretpostavimo da je w1,2 centar nekog xestougla. Na njemu onda
moraju biti rasporeena temena w1,3, w1,7, w1,8, w2,3, w2,5 i w2,7. Pos-
matramo temena w2,5 i w2,7 na xestouglu. Mogui su sledei sluqajevi:
58
a) Temena w2,5 i w2,7 su susedna na tom xestouglu (slika 10a). Tri-
angulacija se dalje ne moe proxiriti jer jedino teme iz skupa svih
temena susedno njima je teme w2,3 koje mora biti na xestouglu.
b) Ako ih razdvaja jedno teme to moe biti samo teme w2,3 (slika 10b).
Kako w1,3 nije susedno ni sa w2,5 a ni sa w2,7, ono mora biti antipodalno
sa w2,3. Onda teme w1,8 nema mesta na xestouglu.
v) Ako su temena w2,5 i w2,7 antipodalna (slika 10v), onda za teme w1,3
nema mesta na xestouglu.
3) |R2| = 3. Ovde imamo 2 mogunosti.
3.1) |R1| = 2. Onda R ∼= Z2 × Z3, pa je γ(L(TΓ(R))) = 0 prema teoremi
89.
3.2) |R1| = 3. Onda je R ∼= Z3 × Z3 i |Z(R)| = 5. Odavde je δ(TΓ(R)) = 4
i δ(L(TΓ(R))) = 6. Ako je utapanje mogue, onda prema tvrenju 6 sva
temena moraju imati stepen 6. Ovo nije taqno, npr. deg([(0, 1), (2, 2)]) = 7.
Kako je L(TΓ(Z2 × Z2)) planaran dokaz je ovim zavrxen.
Ostaje da se ispita lokalan sluqaj.
Teorema 93. Neka je R konaqan lokalan prsten koji nije polje. Tada je
γ(L(TΓ(R))) = 1 akko je R ∼= Z9 ili R ∼= Z3[X]/(X2).
Dokaz: Neka je M = Z(R) maksimalan ideal prstena R. Prema lemi 91,
dovoljno je ograniqiti se na sluqaj |M | ≤ 5. Najpre emo dokazati da
se ovde moe iskljuqiti i sluqaj |M | = 5.
Neka je |M | = |Z(R)| = 5 i x ∈ Reg(R). Tada, deg(x) = 5 prema lemi 82.
Mora postojati y ∈ Reg(R) takav da je x susedan sa y u TΓ(R), odnosno
x + y ∈ Z(R) (u suprotnom bi teme x bilo susedno sa 0). Ivica x— y
spaja dva temena stepena 5 u TΓ(R), pa teme [x, y] iz L(TΓ(R)) ima stepen
8. Kako je meutim δ(TΓ(R)) = 4, to je δ(L(TΓ(R))) = 6. Prema tvrenju 6,
u sluqaju toroidalnosti sva temena grafa L(TΓ(R)) moraju imati stepen
6, xto nije sluqaj jer je deg([x, y]) = 8.
Neka je |R| = pk. Razmatramo samo sluqajeve p = 2 i p = 3.
59
1) |R| = p2. Mogunosti su Fp2, Zp[X]/(X2) i Zp2. Kako R nije polje
i kako su linijski grafovi za Z2[X]/(X2) i Z22 planarni, ostaju samo
mogunosti Z3[X]/(X2) i Z32. Lako se vidi da oba prstena imaju totalne
grafove izomorfne sa K3 ∪ K3,3. Kako je γ(L(K3,3)) = 1, to su njihovi
linijski grafovi toroidalni kao unija toroidalnog i planarnog grafa.
2) |R| = p3. Prema [19] mogunosti su Fp3, Fp[X]/(X3), Zp2 [X]/(pX,X2),
Fp[X, Y ]/(X, Y )2, Zp3 i Zp2 [X]/(pX,X2 − εp), gde ε nije kvadrat u F∗p. Kako
je Fp3 polje i kako su prema teoremi 90 linijski grafovi za Z2[X]/(X3),
Z4[X]/(2X,X2), F2[X,Y ]/(X,Y )2, Z23 i Z4[X]/(2X,X2 − 2) planarni, ostaju
nam F3[X]/(X3), Z9[X]/(3X,X2), F3[X,Y ]/(X,Y )2, Z27 i Z9[X]/(3X,X2 − 3).
Lako je videti da je kod njih |M | = |Z(R)| = 9, pa prema lemi 91 ovde
nema linijskih grafova roda 1.
3) |R| = p4.
3.1) p = 3 i |R| = 81, pa |M | ∈ {1, 3, 9, 27}. Sluqaj |M | = 1 otpada
jer R nije polje, dok sluqaj |M | = 3 otpada jer je onda |R| ≤ 9. Ostali
sluqajevi otpadaju jer ima previxe delitelja nule.
3.2) p = 2 i |R| = 16, pa |M | ∈ {1, 2, 4, 8}. Sliqnom analizom ostaje
nam samo sluqaj |M | = 4, odnosno prsteni F4[X]/(X2) i Z4[X]/(X2+X+1).
Njihovi linijski grafovi su planarni prema teoremi 90.
4) |R| = pk, k ≥ 5. Ovde jasno nema toroidalnih linijskih grafova
jer je |M | = |Z(R)| ≥ 8.
Lista konaqnih komutativnih prstena sa jedinicom za koje je L(TΓ(R))
toroidalan:
Z9, Z3[X]/(X2).
Teorema 94. Neka je g ≥ 0 ceo broj. Tada postoji samo konaqno mnogo
neizomorfnih komutativnih prstena R takvih da je γ(L(TΓ(R))) = g.
Dokaz: Dokazali smo da za g = 0 postoji samo 11 takvih prstena, dok za
g = 1 postoje samo 2 takva prstena. Pretpostavimo da je g ≥ 2. Prema
60
teoremi 85, nejednakost iz tvrenja 6 za graf L(TΓ(R)) svodi se na:
2|Z(R)| − 4 ≤ 6 + 12g − 12
n
.
Kako je
n = |V (L(TΓ(R)))| ≥ 1
2
|R|(|Z(R)| − 1),
zamenom u prethodnu nejednakost dobijamo
|R|(|Z(R)| − 1)(|Z(R)| − 5) ≤ 12g − 12.
Odavde, za |Z(R)| ≥ 6 vai
|R| ≤ 3g − 3.
S druge strane, kako je |R| ≤ |Z(R)|2, ima samo konaqno mnogo sluqajeva
takvih da je |Z(R)| < 6. Ovim je dokaz zavrxen.
Napomena 95. Koristei iste argumente kao u prethodnom dokazu, zan-
imljivo je istai da za |Z(R)| ≥ 6 ne postoji prsteni qiji linijski
grafovi imaju rod 2 ili 3.
61
GLAVA 6
GRAF PRESEKA IDEALA
Neka je R komutativan prsten sa jedinicom i G(R) njegov graf preseka
ideala. U ovoj glavi dajemo klasifikaciju svih toroidalnih grafova
koji su grafovi preseka ideala. Takoe dajemo jedno poboljxanje pos-
tojeih rezultata o planarnosti ovih grafova.
Neka je R komutativan prsten sa jedinicom i neka je I∗(R) skup nje-
govih netrivijalnih ideala. Graf preseka ideala G(R) definixe se na
sledei naqin:
V (G(R)) := I∗(R), E(G(R)) := {{I1, I2} : I1 ∩ I2 6= 0},
gde V (G(R)) (E(G(R))) oznaqava skup temena (ivica) grafa G(R). Ovaj
graf definisan je u radu [18], za nekomutativan prsten R i familiju
levih netrivijalnih ideala u R. Autori su dali potrebne i dovoljne
uslove za povezanost ovog grafa. Za komutativan prsten sa jedinicom R,
G(R) bie nepovezan akko je R direktan proizvod dva polja ([18, posled-
ica 2.8]). Osobine ovog grafa takoe su ispitivane u [3]. U ovom radu
karakterixu se svi prsteni R za koje je cl(G(R)) konaqan i dokazuje se
da iz cl(G(R)) < ∞ sledi χ(G(R)) < ∞. Takoe se dokazuje da vai
diam(G(R)) ≤ 2 u sluqaju kada je G(R) povezan.
U radu [31], autori su okarakterisali one planarne grafove koji
mogu biti grafovi preseka ideala za neke komutativne prstene. Ova
klasifikacija nije data u potpunosti, jer se dokazuje da se mogu pojav-
iti zvezda grafovi, bez detalja o tome koji od njih mogu biti grafovi
preseka ideala. Dopuniemo ovu klasifikaciju u teoremi 97.
Kako struktura ideala odraava osobine prstena prirodno je nas-
taviti dalja istraivanja ovog grafa. U ovoj glavi bavimo se uglavnom
pitanjem njegove toroidalnosti (i u manjem obimu planarnosti). Cilj je
da potpuno opixemo one toroidalne grafove koji mogu biti grafovi pre-
seka ideala za neke komutativne prstene sa jedinicom. Glavni rezultat
dat je u teoremi 110 gde je prezentovano rexenje ovog problema.
6.1 O planarnosti grafa G(R)
Tvrenje 96. Ako G(R) ima konaqan rod, onda je R Artinov prsten. Ako
posmatramo R kao jedan R-modul, onda je l(R) ≤ 5 ako je G(R) planaran i
l(R) ≤ 8 ako je G(R) toroidalan.
Dokaz: Ovo je oqigledno. Ako R ne bi bio Artinov, onda bi G(R)
sadrao Kn kao podgraf (za svako n). Kako je R tada Neterin, on ima
konaqnu duinu kao R-modul i ta duina ima navedene gornje granice.
Moemo se dakle koncentrisati na Artinove prstene. Prema teoremi 1
R ∼= R1 × · · · ×Rn (6.1.1)
gde su Ri lokalni Artinovi prsteni sa maksimalnim idealima Mi. U
[31], autori su opisali planarne grafove koji mogu biti grafovi pre-
seka ideala za neke komutativne prstene. Meu njima, pojavljuju se
i zvezda grafovi. Kako nije data potpuna analiza o kojim se zvezda
grafovima radi, daemo je ovde.
63
Teorema 97. Neka je R lokalan komutativan prsten sa maksimalnim ide-
alom M = 〈x, y〉. Ako je G(R) planaran, onda je M2 = 0 i G(R) je ili
beskonaqan zvezda graf ili je izomorfan sa K1,pk+1, za neki prost broj p i
pozitivan ceo broj k.
Dokaz: Pretpostavimo da je x2 6= 0. Lako je proveriti da su u tom
sluqaju ideali 〈x〉, 〈x2〉, 〈x2, y〉, 〈x2, x+y〉 i M razliqiti i da svi sadre
x2. Dakle, K5 je podgraf u G(R). Isti zakljuqak dobija se ako je y2 6= 0.
Iz pretpostavke da je G(R) planaran, mora biti x2 = y2 = 0. Ako je
xy 6= 0 a kako je x2 = y2 = 0, dobijamo xy ∈ 〈x + y〉. Tada ideali 〈x〉, 〈y〉,
〈xy〉, 〈x+ y〉, 〈x, y〉 formiraju K5 unutar G(R).
Odavde mora da vai x2 = y2 = xy = 0, tj. M2 = 0. Dakle, svaki
element u M je oblika αx+ βy, gde je α, β ∈ U(R)∪ {0} (sa U(R) oznaqeni
su invertibilni elementi u R). Nije texko opisati strukturu ideala u
takvom prstenu. Svi pravi ideali razliqiti od M moraju biti glavni,
oblika 〈x〉, 〈y〉 ili 〈x + αy〉, gde je α ∈ U(R). Ovi ideali su oqigledno
minimalni i trivijalno se seku. U minimalnom sluqaju U(R) = {1},
postoje tri takva ideala.
Dokaimo da je 〈x+ αy〉 = 〈x+ βy〉 ako i samo ako α− β ∈M .
Najpre, ako je α−β ∈M , onda je x+αy = x+(α−β+β)y = x+βy. S druge
strane, ako je 〈x+αy〉 = 〈x+ βy〉, onda x+αy = a(x+ βy) za neko a ∈ R, pa
(1− a)x ∈ 〈y〉 i (aβ − α)y ∈ 〈x〉. Kako M nije generisan jednim elementom,
mora da vai 1−a ∈M i aβ−α ∈M . Dakle, β−α = β(1−a)+aβ−α ∈M .
Iz ove analize izvodi se zakljuqak da za takav prsten R mora da
vai |I∗(R)| = |R/M |+2 (jedan maksimalan ideal i svi razliqiti glavni
ideali koje smo prethodno pomenuli). Ako je R/M beskonaqno polje,
onda ima beskonaqno mnogo ideala. Svi ideali koji nisu maksimalni
susedni su samo sa M (svi su minimalni), pa je G(R) zvezda graf. Ako
polje nije beskonaqno, onda mora imati pk+2 temena (za neki prost broj
p i pozitivan ceo broj k), pa je G(R) ∼= K1,pk+1.
64
Napomena 98. Sve ove grafove moemo dobiti izborom polja F u prstenu
F [X,Y ]/〈X, Y 〉2. Kako je svaki zvezda graf planaran, prethodna teorema
takoe pokazuje koji zvezda grafovi mogu biti grafovi preseka ideala
(zvezda grafovi pojavljuju se samo u sluqaju kada je R lokalan prsten
qiji maksimalan ideal ima taqno dva generatora).
6.2 Toroidalnost grafa G(R)
Poqinjemo ovo poglavlje predstavljanjem grafa Γ, koji se moe uto-
piti u torus (Slika 11 na kraju). Ovaj graf je od suxtinske vanosti za
naxu diskusiju jer su svi toroidalni grafovi G(R) podgrafovi grafa
Γ. Primetimo da Γ nastaje od kompletnog grafa K7 dodavanjem nekih
temena i ivica.
Tvrenje 99. Ako u proizvodu (6.1.1) vai n ≥ 3, onda je γ(G(R)) 6= 1.
Dokaz: Treba samo ispitati sluqaj kada je n = 3 i bar jedan od Ri nije
polje (videti [31]).
Pretpostavimo da je R1 lokalan prsten sa maksimalnim idealom M1 6=
0. Ideali I1 = R1×0×0, I2 = R1×R2×0, I3 = R1×0×R3, I4 =M1×R2×R3,
I5 =M1×R2× 0, I6 =M1× 0×R3, I7 =M1× 0× 0 i I8 = 0×R2×R3 indukuju
podgraf u G(R). Stepeni od I1 i I7 su 6, stepen I8 je 5, dok ostala temena
imaju stepen 7 (u ovom podgrafu). Zakljuqujemo da je e = 26. Ako bi se
ovaj podgraf mogao utopiti u torus, bilo bi f = 18, ali onda dobijamo
kontradikciju jer mora da vai 2e ≥ 3f .
Tvrenje 100. Pretpostavimo da je R ∼= R1 × R2, gde su R1, R2 lokalni
prsteni. Tada je γ(G(R)) = 1 u taqno jednom od sledeih sluqajeva:
1) Jedan od prstena je glavnoidealski domen sa maksimalnim idealom
M takvim da je M4 = 0 a drugi prsten je polje;
65
2) R1 i R2 su glavnoidealski domeni kod kojih su kvadrati maksimalnih
ideala jednaki nuli.
Dokaz: Ako su R1 i R2 polja, onda je G(R) graf sa dva temena bez ivica,
pa je γ(G(R) = 0.
Dokaimo sledee: ako R1 nije polje, onda je glavnoidealski domen.
Pretpostavimo da maksimalni idealM1 nije glavni. Neka je x ∈M1 i y ∈
M1\〈x〉. Pogledajmo ideale R1×0, M1×0, 〈x〉×0, 〈y〉×0, 〈x+y〉×0, M1×R2,
〈x〉 × R2, 〈y〉 × R2, 〈x + y〉 × R2 i 0 × R2. Procenjivanjem njihovih stepena
(na primer, stepen od 〈x〉 × 0 je najmanje 4), dobijamo da u minimalnom
sluqaju imamo podgraf od G(R) sa 10 temena i 31 ivicom. Ako bi se ovaj
podgraf mogao utopiti u torus, dobili bi f = 21. Ovo je kontradikcija
jer mora da vai 2e ≥ 3f .
Zato je R1 lokalan Artinov prsten sa maksimalnim idealom M1 = 〈x〉,
x 6= 0. Dakle
I∗(R1) = {〈xk〉 | 1 ≤ k ≤ r − 1},
gde je r najmanji prirodan broj za koji je xr = 0. U zavisnosti od r i od
prstena R2 imamo nekoliko sluqajeva.
1. r = 2 i R2 je polje. Znamo da je tada G(R) planaran (videti [31]).
2. r = 3 ili r = 4 i R2 je polje. Za r = 3, graf preseka ideala G(R)
izomorfan je sa Γ[1, 2, 3, 4, 5, a], dok je za r = 4 G(R) izomorfan sa
Γ[1, 2, 3, 4, 5, 6, 7, d], pa je roda 1.
3. r ≥ 5. Tada je γ(G(R)) > 1. Ovo je oqigledno, jer u tom sluqaju
〈x〉 × 0, R1 × 0, 〈x2〉 × 0, 〈x3〉 × 0, 〈x4〉 × 0, 〈x〉 ×R2, 〈x2〉 ×R2 i 〈x3〉 ×R2
daju K8.
4. R1 i R2 su lokalni sa maksimalnim idealima M1 = 〈x〉, M2 = 〈y〉,
takvim da je x2 = y2 = 0. Tada je graf preseka ideala G(R) izomor-
fan sa Γ[1, 2, 3, 4, 5, 6, 7]− {36, 37, 46, 47} i γ(G(R)) = 1.
66
5. R1 i R2 su lokalni sa maksimalnim idealima M1 = 〈x〉, M2 = 〈y〉,
takvim da je x2 6= 0 ili y2 6= 0. Tada je γ(G(R)) > 1. Naime, ako je
x2 6= 0, onda 〈x〉×0, 〈x〉×〈y〉, 〈x〉×R2, R1×0, R1×〈y〉, 〈x2〉×0, 〈x2〉×〈y〉
i 〈x2〉 ×R2 daju K8. Sliqno za y2 6= 0.
Ostaje da razmotrimo sluqaj lokalnog Artinovog prstena R sa mak-
simalnim idealom M 6= 0. Kako je M konaqno generisan diskutovaemo
po minimalnom broju generatora (n).
Tvrenje 101. Ako je n ≥ 3, onda je γ(G(R)) > 1.
Dokaz: Dovoljno je razmotriti minimalan sluqaj M = 〈x, y, z〉. Ideali
〈x〉, 〈x+ y + z〉, 〈x, y〉, 〈x, z〉, 〈y, z〉, 〈x, y, z〉, 〈x, y + z〉, 〈y, x+ z〉 i 〈z, x+ y〉 su
razliqiti. Raqunanjem njihovih (minimalnih) stepena dobijamo graf sa
9 temena i 29 ivica. Ako bi se mogao utopiti u torus dobili bi f = 20,
ali to nije mogue jer je 3f = 60 > 58 = 2e.
Nadalje emo qesto morati da proveravamo da li su izvesni ide-
ali jednaki. Da bi uprostili i skratili proveru, dokazaemo jedan
rezultat koji nam omoguava da utvrdimo da je maksimalan ideal ra-
zliqit od ostalih ideala koji se kasnije javljaju u diskusiji. Ovo je
poznati rezultat, ali emo dati dokaz zbog kompletnosti izlaganja. Is-
taknimo najpre jedno poznato tvrenje koje je posledica leme Nakajame
(podseamo da je pretpostavka uslova da je prsten Neterin ukljuqena
pretpostavkom da je lokalan).
Tvrenje 102. Neka je (R,M) lokalan prsten. Ako je I ideal u R takav da
je I +M2 =M , onda je I =M .
Posledica 103. Neka je (R,M) lokalan komutativan prsten. Ako je n
minimalan broj generatora za M i ako je {x1, . . . , xn} bilo koji generixui
skup za M , tada nijedan od elemenata xi ne pripada M2.
Dokaz: Ako na primer xn ∈ M2, onda primenimo prethodno tvrenje na
ideal I = 〈x1, . . . , xn−1〉.
67
Napomena 104. Ovo u suxtini odgovara qinjenici da M/M2 ima dimen-
ziju n kao vektorski prostor nad R/M .
Pored toga, primetimo da u lokalnom prstenu R sa maksimalnim ide-
alom M , za svako a, b ∈ R\{0} vai: 〈a〉 = 〈b〉 akko a = rb za neko r ∈ U(R).
Naime ako 〈a〉 = 〈b〉, onda a = rb i b = sa, za neke r, s ∈ R. Dakle, a = rsa
i (1− rs)a = 0. Kako je a 6= 0, sledi da 1− rs ∈M , pa rs ∈ U(R).
Sada se koncentrixemo na sluqaj kada M nije glavni, ali je gener-
isan sa dva elementa. Kako qesto radimo sa poljem R/M , oznaqiemo ga
sa F .
Pre svega, ako je M2 = 0, graf G(R) je planaran (videti [31], ili
teoremu 97), pa nadalje pretpostavljamo da je M2 6= 0.
Lema 105. Ako je polje F (= R/M) beskonaqno, tada graf G(R) nema konaqan
rod.
Dokaz: Zbog uslova za M , imamo da je dimenzija za M/M2 kao vek-
torskog prostora nad F jednaka 2. Ovaj vektorski prostor je unija
svojih jednodimenzionalnih potprostora (i svaka dva od njih u preseku
imaju samo nula vektor). Kako je polje F beskonaqno, postoji beskonaqno
mnogo takvih potprostora (vektorski prostor nad beskonaqnim poljem ne
moe biti unija konaqno mnogo pravih potprostora). Svaki jednodimen-
zioni potprostor W u M/M2 je oblika I/M2 za neki ideal I koji sadri
M2(6= 0). Zbog toga postoji beskonaqno mnogo razliqitih ideala u R
koji sadre M2(6= 0), pa se netrivijalno seku. Zakljuqujemo da za svako
n, G(R) sadri kompletan podgraf sa n temena. Dakle, on ne moe imati
konaqan rod.
Nadalje, pretpostavljamo da je F konaqno polje.
Lema 106. Ako je R lokalan prsten sa maksimalnim idealom M sa dva
generatora i G(R) je toroidalan, onda je M2 glavni ideal.
68
Dokaz: Pretpostavimo suprotno, neka M2( 6= 0) nije glavni. Dakle pos-
toje neki elementi u, v ∈ M2, takvi da u 6∈ 〈v〉 i v 6∈ 〈u〉. Jasno je da
su ideali 〈u〉, 〈v〉, 〈u + v〉 i M2 razliqiti. Znamo da je M/M2 unija
jednodimenzionih potprostora. Kako je |M/M2| = |F |2, zakljuqili smo
da ima |F | + 1 jednodimenzionih potprostora u M/M2, dakle najmanje 3
takva. Dobijamo tri ideala I1, I2 i I3 koji sadre M2(6= 0). Tako imamo
osam ideala: M , I1, I2, I3, M2, 〈u〉, 〈v〉, 〈u + v〉. Prvih pet ideala imaju
stepen 7 dok poslednja tri imaju stepen (najmanje) 5. Posmatrajui pod-
graf u G(R) indukovan tim idealima, zakljuqujemo da je e ≥ 25. Dakle,
2e− 3f = 2e− 3e+ 24 = 24− e < 0, xto je nemogue.
Teorema 107. Neka je R lokalan prsten sa maksimalnim idealom M sa dva
generatora i neka je G(R) toroidalan. Tada je M3 = 0 i mogu se odabrati
generatori u, v za M tako da je M2 = 〈uv〉, gde je u2 = v2 = 0, ili M2 = 〈u2〉,
gde je uv = 0.
Dokaz: Neka je M = 〈x, y〉. Prema prethodnoj lemi, znamo da je M2 glavni
ideal. Dakle, M2 = 〈ax2 + bxy + cy2〉. Kako je M2 6= M3, bar jedan od
a, b, c mora biti invertibilan. Neka je na primer a ∈ U(R). Moe se
pretpostaviti da je a = 1, pa dobijamo M2 = 〈x2 + bxy + cy2〉. Odavde,
x2 = α(x2 + bxy + cy2). Ako je α ∈ U(R), dobijamo M2 = 〈x2〉. U suprotnom,
1 − α ∈ U(R) i x2 = (1 − α)−1α(bxy + cy2). Zato je M2 = 〈dxy + ey2〉, za
neke d, e. Nastavljamo na isti naqin. Bar jedan od d, e je invertibilan.
Pretpostavimo da je d ∈ U(R) i uzmimo d = 1. Na taj naqin, M2 =
〈xy + ey2〉. Dobijamo xy = β(xy + ey2), za neko β. Ako je β ∈ U(R), onda je
M2 = 〈xy〉, a ako je β ∈M , onda je M2 = 〈y2〉.
Dokazali smo da je jedan od x2, xy, y2 generator za M2.
1) M2 = 〈x2〉. Onda je xy = ax2, za neko a ∈ R. Dakle, x(y−ax) = 0. Ako
odaberemo generatore u = x i v = y − ax za M , dobijamo da je M2 = 〈u2〉
i uv = 0. Vai v2 = ru2, za neko r ∈ R. Kako je uv = 0, dobijamo
v3 = uv2 = u2v = 0.
69
Pretpostavimo da je u3 6= 0. Ideali: 〈u〉, 〈u2〉, 〈u3〉, 〈u, v〉, 〈u + v〉,
〈u2+v〉, 〈u2, v〉, 〈u3, v〉 sadre u3 6= 0 jer je uv = 0. Treba samo proveriti da
su meusobno razliqiti jer e iz toga slediti da G(R) nije toroidalan
budui da sadri K8 kao podgraf.
Znamo da je maksimalan ideal razliqit od ostalih. Takoe, kako
v 6∈ 〈u〉, prva tri ideala razlikuju se od ostalih. Pored ovih, treba jox
proveriti sledee sluqajeve.
1. Ako je 〈u+ v〉 ⊆ 〈u2, v〉, sledi da je u+ v = r(u2 + v) za neko r ∈ R, pa
je u(1− ru) = (r − 1)v. Kako je 1− ru invertibilan dobijamo u ∈ 〈v〉,
xto je nemogue.
2. Ako je 〈u2, v〉 ⊆ 〈u2+ v〉, onda je u2 = r(u2+ v) za neko r ∈ R. Mnoei
sa u i koristei osobinu uv = 0, dobijamo u3 = ru3. Kako je u3 6= 0,
sledi da je 1− r ∈M tj. r ∈ U(R), pa je v ∈ 〈u〉.
3. Ako je 〈u2, v〉 ⊆ 〈u3, v〉, onda je u2 = ru3+ sv za neke r, s ∈ R. Mnoei
sa u dobijamo u3 = ru4, pa je u3(1 − ru) = 0. Kako je 1 − ru ∈ U(R),
dobijamo u3 = 0.
Dakle M3 = 0 i generatori za M mogu se odabrati na eljeni naqin.
2) M2 = 〈xy〉. Ovde vai x2 = axy i y2 = bxy za neke a, b ∈ R. Ako je
bar jedan od a, b invertibilan, moemo odabrati nove generatore u = x,
v = x − ay (ili v = x − by), tako da je M2 = 〈u2〉 i uv = 0. Na taj naqin
ovaj sluqaj svodi se na prethodni. Pretpostavimo zato da su a, b ∈ M .
Dakle x2, y2 ∈ M3. Ali kako je M3 = 〈x3, x2y, xy2, y3〉, zakljuqujemo da je
M3 ⊆ M4, jer su mu svi generatori iz M4. Odavde je M3 = M4. Prema
lemi Nakajame M3 = 0 i x2 = y2 = 0.
Teorema 108. Neka je R lokalan prsten i M = 〈x, y〉, gde su x, y mini-
malni generatori. Tada, γ(G(R)) = 1 ako i samo ako je M2 glavni ideal
i |R/M | ≤ 4. Graf G(R) tada je izomorfan jednom od grafova K5, K6, K7,
Γ[1, 2, 3, 4, 5, a, b], Γ[1, 2, 3, 4, 5, 6, a, b, c] ili Γ− {3d}.
70
Dokaz: Prema prethodnim rezultatima dovoljno je razmotriti sledea
dva sluqaja: M2 = 〈xy〉 6= 0, gde je x2 = y2 = 0 i M2 = 〈x2〉 6= 0, gde je
xy = 0.
M2 = 〈xy〉, x2 = y2 = 0. Opiximo strukturu pravih ideala u prstenu
R.
Pogledajmo najpre glavne ideale. Ako je I = 〈ax+ by〉 za neke a, b ∈ R,
onda, ako je a, b ∈M , imamo da je I = 〈xy〉 ili I = 0. Pretpostavimo zato
da bar jedan od a, b nije u M , na primer neka je a ∈ U(R). Tada 〈ax+by〉 =
〈x + αy〉. Ako je α ∈ M , dobijamo 〈x + αy〉 = 〈x + cxy〉 = 〈x(1 + cy)〉 = 〈x〉.
Dakle dobija se da su glavni ideali sledei:
〈xy〉, 〈y〉, 〈x+ αy〉, za neko α ∈ U(R) ∪ {0}.
Pokaimo da je 〈x+ αy〉 = 〈x+ βy〉 ako i samo ako α− β ∈M .
α− β ∈M . Dakle, α − β = cx + dy za neke c, d ∈ R. Lako se proverava da
je x+ αy = (x+ βy)(1 + cy), pa 〈x+ αy〉 = 〈x+ βy〉.
〈x+ αy〉 = 〈x+ βy〉. Onda je x+αy = r(x+βy), pa (1− r)x = (rβ−α)y. Kako
su x i y minimalni generatori za M , mora da vai 1 − r, rβ − α ∈ M .
Tada α− β = (−1)(rβ − α)− β(1− r) ∈M .
Neka je I ideal koji nije glavni. On mora sadrati bar jedan element
oblika x + αy, gde je α ∈ U(R) ∪ {0} (u suprotnom, svaki element iz I je
oblika ay za neko a ∈ R, odakle sledi da je I = 〈y〉 ili I = 〈xy〉). Kako I
nije glavni, uzmimo ax+by ∈ I\〈x+αy〉. Tada je 〈x+αy, ax+by〉 = 〈x+αy, cy〉
za neko c ∈ R. Kako je xy ∈ 〈x + αy〉 (xy = y(x + αy)), mora postojati
c ∈ U(R) takav da 〈x + αy, cy〉 = 〈x, y〉 = M . Odavde jedini ideal u R koji
nije glavni je maksimalni ideal.
Dakle svi pravi ideali prstena R su:
〈x, y〉, 〈y〉, 〈xy〉, 〈x+ αy〉 (α ∈ U(R) ∪ {0}).
Svi ovi ideali sadre xy(6= 0) i ima ih 3 + |R/M |. Ako je |R/M | ≥ 5,
onda G(R) nije toroidalan. Dakle mora da vai |R/M | ≤ 4 i G(R) je
kompletan graf sa 3 + |R/M | temena.
71
M2 = 〈x2〉, xy = 0, y2 = ax2, za neko a ∈ U(R). Ovaj sluqaj ne razlikuje
se od prethodnog. Dobijamo da su svi pravi ideali u R:
〈x, y〉, 〈y〉, 〈x2〉, 〈x+ αy〉 (α ∈ U(R) ∪ {0}).
Kao i ranije 〈x+αy〉 = 〈x+βy〉 ako i samo ako α−β ∈M . Svi ovi ideali
sadre x2 6= 0 i zakljuqak je isti kao i u prethodnom sluqaju.
M2 = 〈x2〉, xy = 0, y2 = 0. Ovde je malo drugaqija situacija. Naime,
osim ideala 〈x, y〉, 〈x2〉, 〈x+αy〉, za α ∈ U(R)∪{0}, imamo i ideale 〈x2, y〉 i
〈y+βx2〉, za β ∈ U(R)∪{0}. Vai 〈y+βx2〉 = 〈y+γx2〉 ako i samo ako β−γ ∈M
(zapravo y + βx2 = y + γx2 ako i samo ako β − γ ∈ M). Ovi novi ideali
imaju netrivijalne preseke sa M i 〈x2, y〉, dok ostali ideali sadre
x2 6= 0. Sliqnom analizom kao i u prethodnim sluqajevima dobijamo
traeno tvrenje.
Tvrenje 109. Neka je R lokalan prsten sa maksimalnim idealom M = 〈x〉.
Tada, γ(G(R)) = 1 akko G(R) je izomorfan sa K5, K6 ili K7.
Dokaz: R je glavnoidealski domen i svi njegovi ideali su oblika 〈xk〉,
za k ≥ 1. Kako je G(R) toroidalan, mora da vai x8 = 0 odakle sledi
traeni rezultat.
Sumirajmo prethodno dobijene rezultate u obliku sledee teoreme.
Teorema 110. Neka je R komutativan prsten sa jedinicom. Tada vai
γ(G(R)) = 1 ako i samo ako je G(R) izomorfan jednom od sledeih grafova:
K5, K6, K7, Γ[1, 2, 3, 4, 5, a], Γ[1, 2, 3, 4, 5, 6, 7]− {36, 37, 46, 47},
Γ[1, 2, 3, 4, 5, 6, 7, d], Γ[1, 2, 3, 4, 5, a, b], Γ[1, 2, 3, 4, 5, 6, a, b, c], Γ− {3d}.
72
¢
¢
¢
¢
¢
¢
¢
¢¢AA
A
A
A
A
A
AA´
´
´
´
¡
¡
¡
¡
¶
¶
¶
¶
¶
¶
·
·
·
·
·
·
·
Q
Q
Q
Q
@
@
@
@
S
S
S
S
S
S
T
T
T
T
T
T
T
@
@
@
@
¡
¡
¡
¡
¡
¡
¡
¡
HH
HH
HH
HH
H
¡
¡
¡
¡
@
@
@
@
³³
³³
³³
³³
³³
³³³
¡
¡
¡
¡
¡
¡
¡
¡¡
´
´
´
´
´
´
´
´
´
´
´
´´
¡
¡
¡
¡
¡
¡
¡
¡¡
©©
©©
©©
©©
©
s s
s s
s
s s
s
ss
sss s
s s
s s
5 1 2 5
5 1 2 5
6
7
6
7
4
3
d
c
b
a
Slika 11. Graf Γ
73
GLAVA 7
ZAKLjUQAK
U ovoj glavi daemo neke zavrxne napomene. Sumiraemo glavne
rezultate ove disertacije i sistematizovati ono xto je uraeno. Kako
problematika pridruivanja grafova prstenima i modulima ostavlja
mnogo otvorenih i zanimljivih pitanja, ovde emo spomenuti i neke od
tih problema koji mogu biti interesantni za dalja istraivanja.
Glavni rezultati i otvorena pitanja glave 2
U glavi 2 odreen je radijus totalnog grafa. Za komutativan prsten
R ispitani su povezanost i dijametar prstena polinoma, prstena for-
malnih redova, idealizacije i prstena matrica nad R.
Jedno od otvorenih pitanja u vezi sa ovom problematikom je pitanje
odreivanja dublje veze izmeu totalnog grafa TΓ(R) i grafa delitelja
nule Γ(R). Druga zanimljiva i jox uvek neistraena tema su totalni
grafovi grupnih prstena.
Ipak, po autorovom ubeenju, najzanimljivija otvorena pitanja vezana
su za regularne elemente komutativnog prstena R takvog da Z(R) nije
ideal u R. Ako je Reg(Γ(R)) povezan, onda je TΓ(R) povezan ([7, teo-
rema 3.1]). Primer komutativnog prstena R = Q[X](+)(Q(X)/Q[X]) ([7,
primer 3.2]) pokazuje da obratno ne mora da vai. U ovom primeru
je diam(TΓ(R)) = 2 i diam(Reg(Γ(R))) = ∞. Posledica 13 daje sledeu
procenu: ako je diam(TΓ(R)) = n, onda je diam(Reg(Γ(R))) ≥ n− 2.
Prvo pitanje koje treba postaviti ovde je da li se moe desiti sluqaj
m = diam(Reg(Γ(R))) > diam(TΓ(R)) = n?
Odgovor je verovatno negativan. Ako nije, onda treba nai primer
takvog prstena R (koji svakako nije Neterin).
Xto se radijusa tiqe, dokazali smo da je r(TΓ(R)) = diam(TΓ(R))
ako je TΓ(R) povezan. Moe se postaviti pitanje odreivanja radijusa
r(Reg(Γ(R))) kada je Reg(Γ(R)) povezan.
Ako je diam(TΓ(R)) = n, koristei dodatnu pretpostavku da je R Ne-
terin, dobija se sledea nejednakost ([1, posledica 1]):
n− 2 ≤ diam(Reg(Γ(R))) ≤ n.
U vezi sa poslednjom nejednakoxu mogu se postaviti neka zanimljiva
pitanja. Prvo, da li se uslov da je R Neterin moe oslabiti? Korisno
bi bilo i nai primere gde je diam(Reg(Γ(R))) ∈ {n− 2, n − 1, n}. U vezi
sa radijusom postaviemo sledeu hipotezu:
Neka je R komutativan Neterin prsten. Ako je TΓ(R) povezan, konaqnog
dijametra, onda je r(Reg(Γ(R))) = diam(Reg(Γ(R))).
75
Glavni rezultati i otvorena pitanja glave 3
U ovoj glavi uveden je totalni graf TΓ(M) R-modula M nad komu-
tativnim prstenom R. On predstavlja generalizaciju totalnog grafa
prstena TΓ(R). Ispitana je njegova struktura i neke od osobina. Is-
traeno je kako se veze izmeu grafova TΓ(M) i TΓ(R) reflektuju na veze
komutativnog prstena R i modula M nad njim. Teorema 38 iz ove glave
predstavlja dobar primer kako ispitivanje svojstava nekog grafa moe
dovesti do qisto algebarskih pitanja, kao xto je pitanje kada torzioni
elementi modula formiraju podmodul.
U vezi sa tim istaknimo dalje mogunosti za rad sa grafovima koji
su pridrueni modulima. Neka je R prsten sa jedinicom (R ne mora biti
komutativan) i M levi R-modul. Torziona podgrupa T (M) definixe se
sa
T (M) = {x ∈M | AnnR(x) sadri regularni element}.
Ovde pod regularnim elementom r ∈ R podrazumevamo element koji nije
delitelj nule (ni levi ni desni). Zanimljivo je videti xta se dobija
ako se definicija grafa bazira na ovoj definiciji. Glavni cilj je nar-
avno dobiti xto vixe informacija o strukturi torzione podgrupe T (M)
i njenim vezama sa prstenom R. Dobijanje novih korisnih informacija
opravdalo bi uvoenje takvog grafa.
Glavni rezultati i otvorena pitanja glave 4
Ve smo ranije napomenuli da je glava 4 centralno mesto ove dis-
ertacije. Sa ciljem boljeg sagledavanja klase qistih prstena, u ovoj
glavi definisan je qisti graf CΓ(R). Detaljno je ispitana njegova struk-
tura i dati su uslovi pod kojima je on povezan, kao i uslovi pod kojima je
njegov dijametar konaqan. Ispitane su veze qistog grafa kako sa qistim
prstenima, tako i sa drugim klasama prstena. Izmeu ostalog dokazano
76
je da je diam(CΓ(R)) ≤ 2 ako je R qist ili 2-dobar prsten. Do na izomor-
fizam su odreeni svi konaqni komutativni prsteni za koje je CΓ(R)
planaran ili toroidalan. Glavno otvoreno pitanje ve je postavljeno
pri analizi dijametra, ali emo ga ovde ponoviti:
Da li postoji komutativan En-prsten R takav da je diam(CΓ(R)) > 2 ?
Naalost mi ovde nismo uspeli da konstruixemo takav prsten niti
da opovrgnemo njegovo postojanje. Osim ovog, postoje i druga pitanja u
vezi sa qistim grafom koja mogu biti zanimljiva za dalja istraivanja.
Jedno od takvih pitanja moe biti odreivanje radijusa qistog grafa.
Valjalo bi ispitati i xta se dexava ukoliko na potpuno isti naqin
definixemo graf CΓ(R) za nekomutativan prsten R. Posebnu panju
ovde bi trebalo obratiti na prstene matrica qija bogata struktura
daje dosta prostora za dalji rad.
Glavni rezultati i otvorena pitanja glave 5
Glava 5 bavi se linijskim grafom L(TΓ(R)) totalnog grafa komuta-
tivnog prstena. Glavni rezultati ove glave tiqu se problema utapanja
linijskog grafa. Kompletno su (do na izomorfizam) klasifikovani svi
komutativni prsteni takvi da su njihovi linijski grafovi planarni ili
toroidalni. Osim toga, dokazano je da za g ≥ 0 postoji samo konaqno
mnogo komutativnih prstena takvih da je γ(L(TΓ(R))) = g.
Prirodno je kao jednu od ideja za dalji rad, postaviti pitanje da li
se sliqni rezultati mogu dobiti za L(CΓ(R)), gde je CΓ(R) qisti graf
komutativnog prstena definisan u prethodnoj glavi?
77
Glavni rezultati i otvorena pitanja glave 6
U glavi 6 izloena je kompletna klasifikacija toroidalnih grafova
koji su grafovi preseka ideala nekog komutativnog prstena. Analizom
zvezda grafova dato je i jedno poboljxanje postojeih rezultata o pla-
narnosti grafa preseka ideala. Jedna od zanimljivih tema je uopxtenje
ovih rezultata posmatranjem grafa preseka podmodula datog R-modula
M . Ovako definisan graf ve je postao tema nekih istraivanja.
78
Literatura
[1] S. Akbari, D. Kiani, F. Mohammadi, S. Moradi, The total graph and regular
graph of a commutative ring, J. Pure Appl. Algebra 213 (2009) 2224–2228.
[2] S. Akbari, H.R. Maimani, S. Yassemi, When a zero-divisor graph is planar or
a complete r-bipartite graph, J. Algebra 270 (2003) 169–180.
[3] S. Akbari, R. Nikadish, M.J. Nikmehr, Some results on the intersection graphs
of ideals of rings, ITCP, to appear.
[4] D.D. Anderson, V.P. Camilo, Commutative rings whose elements are a sum of
a unit and idempotent, Comm. Algebra 30 (2002) 3327–3336.
[5] D.D. Anderson, M. Winders, Idealization of a module, J. Comm. Algebra 1/1
(2009) 3–56.
[6] D.F. Anderson, M.C. Axtell, J.A. Stickles, Zero-divisor graphs in commutative
rings, Commutative Algebra, Noetherian and Non-Noetherian Perspectives,
Springer (2010) 23–45.
[7] D.F. Anderson, A. Badawi, The total graph of a commutative ring, J. Algebra
320 (2008) 2706–2719.
[8] D.F. Anderson, P.S. Livingston, The zero-divisor graph of a commutative ring,
J. Algebra 217 (1999) 434–447.
[9] D.F. Anderson, S.B. Mulay, On the diameter and girth of a zero-divisor graph,
J. Pure Appl. Algebra 210 (2007) 543–550.
[10] M.F. Atiyah, I.G. Macdonald, Introduction to commutative algebra, Adison-
Wesley Publishing Company, 1969.
[11] M. Axtel, J. Coykendall, J. Stickles, Zero-divisor graphs of polynomials and
power series over commutative rings, Comm. Algebra 6 (2005) 2043–2050.
[12] M. Axtel, J. Stickles, Zero-divisor graphs of idealizations, J. Pure Appl. Algebra
204 (2006) 235–243.
[13] I. Beck, Coloring of commutative rings, J. Algebra 116 (1988) 208–226.
[14] I. Bozˇic´, Z. Petrovic´, Zero-divisor graphs of matrices over commutative rings,
Comm. Algebra 37 (2009) 1186–1192.
[15] I. Bozˇic´, Z. Petrovic´, Z. Pucanovic´, The clean graph of a commutative ring,
under review.
[16] W. Brown, Matrices Over Commutative Rings, Marcel Dekker, Inc., New York,
1993.
[17] V.P. Camillo, H.P. Yu, Exchange rings, units and idempotents, Comm. Algebra
22 (1994) 4737–4749.
[18] I. Chakrabarty, S. Ghosh, T.K. Mukherjee, M.K. Sen, Intersection graphs of
ideals of rings, Discrete Math. 309 (17) (2009) 5381–5392.
80
[19] B. Corbas, G.D. Williams, Rings of order p5. I. Nonlocal rings, J. Algebra 231
(2) (2000) 677–690.
[20] B. Corbas, G.D. Williams, Rings of order p5. II. Local rings, J. Algebra 231
(2) (2000) 691–704.
[21] J. Coykendall, J. Maney, Irreducible divisor graphs, Comm. Algebra 35 (3)
(2007) 885–896.
[22] R. Diestel, Graph Theory, Third Edition, Graduate Texts in Mathematics 173,
Springer-Verlag Berlin Heidelberg, 2005.
[23] D.E. Fields, Zero-divisors and nilpotents in power series rings, Proc. Amer.
Math. Soc. 27 (1971) 427–433.
[24] N. Ganesan, Properties of rings with a finite number of zero divisors, Math.
Ann. 157 (1964) 215–218.
[25] R. Gilmer, A. Grams, T. Parker, Zero divisors in power series rings, J. Reine
Angew. Math. 278/279 (1975) 145–164.
[26] J. Han, W.K. Nicholson, Extensions of clean rings, Comm. Algebra 29 (2001)
2589–2595.
[27] M. Henriksen, Two classes of rings generated by their units, J. Algebra 31
(1974) 182–193.
[28] J. Huckaba, J. Keller, Annihilation of ideals in commutative rings, Pacific J.
Math. 83 (1979) 375–379.
[29] J. Huckaba, Commutative rings with zero divisors, Monographs and Textbooks
in Pure and Applied Mathematics 117, Marcel Dekker, Inc., New York, 1988.
81
[30] Hung-Jen Chiang-Hsieh, Pei-Feng Lee, Hsin-Ju Wang, The embedding of line
graphs associated to the zero-divisor graphs of commutative rings, Israel J.
Math. 180 (2010) 193–222.
[31] S.H. Jafari, N.J. Rad, Planarity of intersection graphs of ideals of rings, Int.
El. J. Algebra 8 (2010) 161–166.
[32] I. Kaplansky, Commutative rings, Revised Edition, University of Chicago Press,
Chicago, 1974.
[33] K. Kuratowski, Sur le proble`me des courbes gauches en topologie, Fund Math.
15 (1930) 271–283.
[34] T.Y. Lam, A First Course in Noncommutative rings, Springer, New York,
2001.
[35] T.G. Lucas, The diameter of a zero-divisor graph, J.Algebra 301 (2006) 174–
193.
[36] H.R. Maimani, C. Wickham, S. Yassemi, Rings whose total graphs have genus
at most one, Rocky Mountain J. Math., to appear.
[37] S. Moconja, Z. Petrovic´, On the structure of comaximal graphs of commutative
rings with identity, Bull. Aust. Math. Soc. 83 (2011) 11–21.
[38] W.K. Nicholson, Lifting idempotents and exchange rings, Trans. Amer. Math.
Soc. 229 (1977) 269–278.
[39] W.K. Nicholson, Y. Zhou, Clean general rings, J. Algebra 291 (2005) 297–311.
82
[40] Z. Petrovic´, Z. Pucanovic´, On the radius and the relation between the total
graph of a commutative ring and its extensions, Publ. Inst. Math. 89(103)
(2011) 1–9.
[41] Z. Petrovic´, Z. Pucanovic´, The line graph associated to the total graph of a
commutative ring, Ars Combinatoria, to appear.
[42] Z. Petrovic´, Z. Pucanovic´, Toroidality of intersection graphs of ideals of com-
mutative rings, under review.
[43] Z. Pucanovic´, The total graph of a module, Matematicˇki vesnik, 63(4) (2011)
305–312.
[44] R. Raphael, Rings which are generated by their units, J. Algebra 28 (1974)
199–205.
[45] S.P. Redmond, Central sets and radii of the zero-divisor graphs of commutative
rings, Comm. Algebra 34 (2006) 2389–2401.
[46] S.P. Redmond, On zero-divisor graphs of small finite commutative rings, Dis-
crete Math. 307 (2007) 1155–1166.
[47] S.P. Redmond, The zero-divisor graph of a non-commutative ring, Internat. J.
Commutative Rings 1 (4) (2002) 203–211.
[48] G. Ringel, Das gescblecht des vollstandigen paaren graphen, Abh. Math. Sem.
Univ. Hamburg 28 (1965) 139–150.
[49] G. Ringel, J. W. T. Youngs, Solution of the Heawood map-coloring problem
Proc. Nat. Acad. Sei. USA 60 (1968) 438–445.
83
[50] P.K. Sharma, S.M. Bhatwadekar, A note on graphical representation of rings
J. Algebra 176 (1995) 124–127.
[51] P. Va´mos, 2-Good rings, Quart. J. Math. (Oxford) 56 (2005) 417–430.
[52] D.B. West, Introduction to graph theory, Prantice Hall, Inc., Upper Saddle
River, NJ, 1996.
[53] H. Whitney, Congruent graphs and connectivity of graphs, American Journal
of Math. 54 (1932) 150–168.
[54] C. Wickham, Classification of rings with genus one zero-divisor graphs, Comm.
Algebra 36 (2) (2008) 1–21.
[55] T. White, Graphs, Groups and Surfaces, North-Holland Math. Studies 188,
Amsterdam, 1984.
[56] G.S. Xiao, W.T. Tong, n-Clean rings and weakly unit stable rings, Comm.
Algebra 33 (2005) 1501–1517.
[57] Y.Q. Ye, Semiclean rings, Comm. Algebra 31 (2003) 5609–5625.
84
Biografija autora
Zoran Pucanovi je roen 16.06.1968. godine u Zajeqaru. Diplomirao
je na Matematiqkom fakultetu u Beogradu (smer Teorijska matematika
i primene) u junu 1995. godine. Magistrirao je u decembru 2002. go-
dine, takoe na Matematiqkom fakultetu u Beogradu, smer Algebra,
odbranivxi rad pod naslovom ,,Prsteni sa jednoznaqnom faktorizaci-
jom”. Od 1995. godine radi kao asistent na katedri za matematiku,
fiziku i nacrtnu geometriju Graevinskog fakulteta u Beogradu.