ماذا يعني أن اثنين من الأشجار الثنائية لتكون isomorphic؟

Question

ماذا يعني أن اثنين من الأشجار الثنائية لتكون isomorphic؟ لقد كنت أبحث عن الإنترنت ولا أستطيع أن أجد تفسيرا واضحا.

بقدر ما أفهم، شجرتان هي Isomorphic إذا كان لديهم نفس الشكل. لذلك أنا أظن أن اثنين من الأشجار متطابقة يمكن أن تحتوي على قيم مختلفة في العقد.

Answer 1

يأتي ISOMORPHIC من اليونانية "نفس الشكل" (مثل ISOBAR هو النقاط مع نفس ضغط الهواء والضغط يعني "الجانب الآخر") لذلك فهمك صحيح. ولكن لا تخطئ في افتراض الشكل في هذه الحالة هو جسدي - بدني الشكل (مثل الشجرة له جذر واحد، عقدة واحدة اليسار والعقدة اليمنى واحدة؛ انظر أدناه على سبيل المثال). علماء الرياضيات لديهم لغتهم الخاصة بعض الأحيان يتحمل علاقة المرور مع اللغة الإنجليزية :-)

انها ليست مجرد الأشجار الثنائية. في الرياضيات، هياكلان هي Isomorphic إذا تم الحفاظ على خصائصها بغض النظر عن تعبيرها (يمكنك الحصول على وظيفة تترجم A إلى B وآخر من B إلى أي خسارة في المعلومات).

لحالتك الخاصة، إنها المعلومات الموجودة في الشجرة المحفوظة. على سبيل المثال، إذا كانت هذه المعلومات هي العناصر الفرز {1,2,3}, ، ثم الشجرة لا يجب أن تكون هي نفسها جسدي - بدني الشكل على الإطلاق - سيكون الاثنين التاليان isomorphic:

  2      1
 / \      \
1   3      2
            \
             3

قائمة مرتبطة مرتبة (أو صفيف فرزها، لهذه المسألة) هي أيضا isomorphic لأولئك الحادين، في هذه الحالة، لن تضيع أي معلومات في التحولات بين الاثنين.

إذا تم استخدام الشجرة الثنائية بطريقة يكون فيها ترتيب الفرز غير ذي صلة (IE، "كيس" نوع من الحاوية)، فستكون المعلومات فقط المحتويات بأي ترتيب، وكل ما يلي سيكون Isomorphic (آخر واحد آخر مجرد حقيبة، آخر هي قائمة):

  2      1           2   3                   +---+  +---+  +---+
 / \      \         /     \      +-------+   | 3 |->| 1 |->| 2 |
1   3      2       1       2     | 1,3,2 |   +---+  +---+  +---+
            \     /         \    +-------+
             3   3           1

بالطبع، قد تعتبر شجرة غير مميزة قليلا من النفايات اعتمادا على احتياجاتك، لكن هذا ليس ذا صلة بهذا المناقشة بالذات.

Answer 2

يجب أن تفي الشروط التالية بأشجار اثنين لتكون Isomorphic:
1. الشجرة هي Isomorphic إذا وفقط إذا حافظت على نفس المستويات ونفس عدد القمم في كل مستوى.

2.Two الأشجار هي isomorphic إذا وفقط إذا كان لديهم نفس الطيف درجة.

3.Two الأشجار هي Isomorphic إذا ولتكون لديها نفس درجة الطيف في كل مستوى.

4. إجمالي عدد سليل الأوراق من قمة الرأس وعدد المستوى من قمة الرأس هي شجرة شجرة الأشجار الثباتي.

بكلمات بسيطة:
شجرتان هي Isomorphic إذا كانت هناك شجرة واحدة يمكن الحصول عليها من غيرها من خلال أداء أي عدد من الاقتباس أي تبديل الأطفال الأيسرين والطفلات المناسبة لعدد من العقدة.

مثال على أشجار ISOMORPHIC:

المرجع: 1.http://www14.in.tum.de/konferenzen/jass03/presentations/eterevsky.pdf. 2.http://www.geeksforgeeks.org/tree-isomorphism-problem/

Answer 3

أعتقد أن تفهمك صحيح جدا. إذا تجاهلت القيم وإلقاء نظرة على الهيكل، فما يتمكن كل عقدة في الشجرة الأولى، يجب أن تكون هناك عقدة مقابلة في الشجرة الأخرى والعكس بالعكس.

بطبيعة الحال، سيكون كلا الشجرتين نفس العدد من العقد. بالإضافة إلى ذلك، يمكنك كتابة خوارزمية (سوبر ساذجة) لتأكيد هذه الأيزيومورفية من خلال محاولة جميع وظائف التعيين الممكنة، وضمان ذلك مقابل كل عقدة في الشجرة الأولى التي يتم تعيينها إلى عقدة في الآخر، يحدث التعيين المقابل مع الوالد ومع الطفلين. هناك خوارزميات فعالة بوضوح للتحقق من ذلك.

قد تستفيد من القراءة الرسم البياني isomorphism. أول؛ الأشجار هي حالة خاصة (وسهولة حلها) لأنها لا تملك دورات.