Zajímá mě, zdali graf může být hamiltonovský, prestože neplatí ani jedna Diracova ani Oreho podmínka.
Díky za info
0x
Aby byl graf Hamiltonovský, tak musí platit, že je tzv. souvislý, navíc, každý Hamiltonovský graf je alespoň 2* souvislý.
Obecně tzv. postačující podmínky jsou používány pro potvrzení, že graf Hamiltonovský je, naopak nutné podmínky jsou používány pro potvrzení, že graf není Hamiltonovský. Takže Oystein Oreova podmínka je tzv. dostačující, aby graf byl Hamiltonovský, přičemž Diracova podmínka je jen důsledkem Oreovy věty. Takže ptáte li se, zda může být graf Hamiltonovský, ačkoliv v něm nebyla potvrzena Oreova podmínka (a tím pádem ani Diracova), tak pokud bude tzv. nutná podmínka nepotvrzena, nebude Hamiltonovský, pokud bude naopak nutná podmínka potvrzena, bude Hamiltonovský. Čili pokud bude zjištěno, že není souvislý, tak opravdu nebude Hamiltonovský, ale pokud bude naopak zjištěno, že je souvislý, tak bude Hamiltonovský.
Neneseme odpovědnost za správnost informací a za škodu vzniklou jejich využitím. Jednotlivé odpovědi vyjadřují názory jejich autorů a nemusí se shodovat s názorem provozovatele poradny Poradte.cz.
Používáním poradny vyjadřujete souhlas s personifikovanou reklamou, která pomáhá financovat tento server, děkujeme.