הפיכת קשתות לקודקודים והפוך בגרפים

[amamk]

הפיכת קשתות לקודקודים והפוך בגרפים

שאלתי היא האם בהנתן גרף G=(v,E) ניתן ואפשרי להפוך אותו כך שכל קודקוד יהווה קשת בגרף החדש,וכל קשת תהיה קודקוד.. באילו תנאים אפשר? האם יש שם לגרפים כאלה? תודה גיא.

 

[Fingertip]

לא בדיוק אפשר

תלוי מה בדיוק אתה רוצה לשמר. לפעמים מספיק להפוך רק את הקשתות לקדקדים, ולהוסיף קשתות חדשות ("היפרקשתות") בין קשתות סמוכות. (כלומר הקודקדים בגרף החדש יהיו סמוכים אחד לשני על ידי היפרקשת, אם ורק אם הקשתות שהם היו בגרף הקודם נגעו בקודקוד משותף) למבנה הזה קוראים "גרף הקשתות". אבל יכול להיות שזה לא בדיוק מה שאתה צריך. מה אתה מנסה לשמר? אהד.

 

[amamk]

האמת שבדיוק הפוך...

התכונה שאני מעוניין בה היא להפוף קודקודים לקשתות... אפשרי?אולי מקרים פרטיים?

 

[Fingertip]

אם תפרט יותר זה יהיה מצויין.

זה קשה סתם להפוך קדקדים לקשתות. צריך "לאבד" או "לשנות" חלק מהמידע, כי סתם ככה להפוך אי אפשר. (קדקד אחד מחבר בין כמה קשתות, אבל קשת מחברת רק בין שני קדקדים או פחות). אהד.

 

[עריסטו]

../images/Emo26.gif

http://en.wikipedia.org/wiki/Line_graph