Transitiv graf
Hur avgör jag om grafen eller matrisen till R1 och R2 är transitiva. Jag kommer fram till att R1 är reflexiv och symmetrisk men vet inte hur jag ska komma fram till om någon av dessa är transitiv. Jag förstår själva konceptet av transitivitet men förstår inte hur jag ska applicera de här
Hur stor är grafen? Om det inte är alltför många noder och kanter, kan du undersöka de kanter som finns för hand. Titta på de noder som har mer än en kant som förbinder dem med andra. Om det finns en kant från A till B och en från B till C, finns det en från A till C direkt? Om det finns kanter från A till B och B till A, finns det en kant från A till A? :)
Smutstvätt skrev:Hur stor är grafen? Om det inte är alltför många noder och kanter, kan du undersöka de kanter som finns för hand. Titta på de noder som har mer än en kant som förbinder dem med andra. Om det finns en kant från A till B och en från B till C, finns det en från A till C direkt? Om det finns kanter från A till B och B till A, finns det en kant från A till A? :)
sorry glömde bifoga bilden haha :)
De här graferna är väldigt små, och då är det nog mest effektivt att titta på de olika kopplingarna i grafen. Om du har en lite större graf går det att undersöka matrisen (i princip en "brute force"-metod), men det är inte särskilt trevligt det heller. Det kanske finns någon mer effektiv metod, men annars är det i princip följande:
- Titta på ett element i matrisen, exempelvis (ev. koppling från x till y).
- Om det finns en koppling där (dvs. elementet är 1), undersök för alla noder z.
- Om något index är ett (dvs. det finns en koppling från nod y till z), kontrollera att elementet är 1.
- Upprepa för alla kopplingar från y till andra noder
- Om det finns en koppling där (dvs. elementet är 1), undersök för alla noder z.
- Upprepa för alla element i matrisen
