6) 5 serva puhul on 1 võimalus. Ühtlasi näen, et 5 serva puhul on iga tipu aste 2. Kui lisada veel üks serv, läheb mõne tipu aste juba 2-st suuremaks. Seega on 5 suurim servade arv, et graaf vastaks ülesandes püstitatud tingimustele. Kokku sain seega moodustatud 11 erinevat graafi. ÜLESANNE 5. Lihtahela koosseisus pole korduvaid servi, seega peab graafis G olema vähemalt üks korduv serv. Vaatan alguses ühte lihtsat lihtahelat. Joonis 1 Iga lihtahela koosseisus on olemas 2 sellist tippu, et kui üks neist eemaldada, jääb graaf ikka sidusaks. Nendeks tippudeks on lihtahela otspunktid ehk joonisel äärmised tipud. Diskreetne matemaatika II Kodused ülesanded 4 Olga Dalton 104493
2. G on sidus, kuid ükskõik millise serva kustutamisel muutub mittesidusaks 3. G ei sisalda tsükleid, kuid ükskõik millise serva lisamisel tekib tsükkel 46. Puu tingimus lihtahelate kaudu. [2] o Teoreem. Graaf G on puu parajasti siis, kui tema iga kahte erinevat tippu ühendab täpselt üks lihtahel. o Tõestus. Tarvilikkus. Olgu G puu. Et puu on sidus, siis G iga kahte tippu u ja v ühendab vähemalt üks lihtahel. Kahte lihtahelat u ja v vahel olla ei saa, sest siis saaksime nende abil konstrueerida tsükli. Piisavus. Ühendagu graafi G iga kahte erinevat tippu täpselt üks lihtahel. G on sidus, sest igast tipust pääseb igasse teise. G on tsükliteta, sest tsükli suvalise serva kahte otspunkti ühendab vähemalt kaks lihtahelat. 47. Märgendatud puu. Märgendatud puu Prüferi kood. Puu taastamine Prüferi koodi järgi. **Tõestus, et taastamisel saadakse igast koodist puu. **Cayley teoreem
annaabi.ee 
