Eulersche Tour ohne Hamiltonpfad und Hamiltonkreis?

Ich brauche einen Graphen mit 7 knoten und 9 kanten und habe dieses hier erstellt. Nur habe ich den zweifel dass es einen hamiltonpfad hat. Kann mir jemand helfen?

Bild zum Beitrag

2 Antworten

Destranix

09.11.2024, 15:16

Offensichtlich gibt es keinen Hamiltonkreis, denn du hast mehrere Engstellen, die du mehrmals besuchen musst, um den Kreis zu schließen.

Einen Hamiltonpfad besitzt der Graph aber trivial.

Annllyjha

Beitragsersteller

09.11.2024, 15:19

Also würde dieser Graph nicht zu einer Aufgabe passen, bei der ich keinen Hamiltonpfad und Hamiltonkreis haben darf oder?

Destranix

09.11.2024, 15:20

@Annllyjha

Nein.

Bau doch einfach zwei oder drei Sackgassen ein, dann hast du keinen Hamiltonpfad.
Odre brauchst du einen Eulerpfad?

Annllyjha

Beitragsersteller

09.11.2024, 15:24

@Destranix

Ja muss ein eulerpfad sein mit 9 kanten und 7 knoten

Destranix

09.11.2024, 15:25

@Annllyjha

Irgendetwas sternartiges könnte denke ich funktionieren. Drei Dreiecke mit gemeinsamen Mittelpunkt oder so etwas.

Annllyjha

Beitragsersteller

09.11.2024, 15:36

@Destranix

Ja das habe ich gerade auch herausgefunden.. danke trotzdem :) 🙏🏻

PeHeReBe

13.11.2024, 12:52

Viele Grüße aus AuD an der tubs . Das Zeichen für Radioaktivität ist übrigens ein solcher graph

Ähnliche Beiträge

Graphentheorie?

Hallo,

gibt es zusammenhängende Graphen bei denen nur ein Knoten einen ungeraden Grad hat?

Wenn ja welche wären das/welche Literatur gibt es dazu? Ich finde im Internet leider nichts brauchbares.

...zum Beitrag

Anzahl der gerichteten Graphen?

Wie kann man die Anzahl der gerichteten Graphen mit n Knoten zählen? Und wie viele davon gibt es?

...zum Beitrag

Eulertour ohne Hamiltonkreis und pfad?

Hi Leute ich brauche einen Graphen, der 7 Knoten und 9 Kanten hat und eine Eulertour ist aber ohne Hamiltonpfad oder kreis. Ich kann mir das aber nicht vorstellen. Kann mir jemand helfen?

...zum Beitrag

Was bedeutet Isomorph?

Wenn zwei Graphen derselben Gestalt und desselben Typs gegeben sind, kann man mithilfe von Matrizen ihre Isomorphie überprüfen.

Was genau meint man mit Gestalt bzw. Typ? Weiß das jemand?

Bei Gestalt könnte ich mir vorstellen gleich viele Knoten/Kanten.

...zum Beitrag

Integral bestimm 0 bis b?

Hallo, ich sitze gerade an meinen Mathehausaufgaben und bin am verzweifeln…

letzte Stunde haben wir das Intervall 0 bis b in streifenbreiten unterteilt und berechnet, wieviele Streifen wir dafür benötigen. In den folgenden zwei Bildern seht ihr, wie wir das berechnet haben. Bis dahin habe ich sogar alles gut verstanden.

In dem Fall ist es ja so, dass Der graph die linke Kante der Rechtecken immer berührt (Abbildung). Also Hausaufgabe sollen wir ebenfalls die anzahlender streifenbreiten berechnen, aber dieses Mal soll der Graph die rechte Seite von den Rechtecken berühren. es muss also auch b^3/3 rauskommen. Als Hilfe hat unser Lehrer und folgende Gleichung gegeben, aber die hilft mir ehrlichgesagt auch nicht wirklich weiter…. n(n+1) (2n+1)/6

wenn ihr mir helfen könntet und mir einen Tipp geben könnt, bin ich euch unnormal dankbar!!!!

...zum Beitrag

Wie funktioniert der Fifo Algorithmus (Operations Research)?

Hallo, ich versuche gerade den Fifo Algorithmus zu verstehen aber im Internet findet man dazu nur etwas in Bezug zu Kostenrechnung. Bei mir geht es aber um Operations Research und um Graphen. Weiß jemand was die Schritte sind um den kürzesten Weg von einem Knoten zum anderen Knoten anhand des Fifo Algorithmus zu berechnen? Vielen dank

...zum Beitrag

Dijkstra Algorithmus?

Hello Leute, was passiert beim Dijkstra Alg wenn der Graph zwei Zusammenhangskomponenten hat? Irgendwann gibt es ja keine Nachfolger mehr, aber die Knoten von der anderen Zusammenhangskomponente wurden ja noch nicht besucht. Ist dann der Algorithmus beendet und es gibt einfach keine Lösung? Danke im Voraus

...zum Beitrag

Geschwulst an der Kehle / Hund

Mein Biewer Yorkshier Terrier, 6 Jahre, Rüde, kastriert, hat am Kehlkopf einen dicken, harten Knoten.... was kann das sein. Kanten sind fühlbar. Der Hund frisst normal, ist aktiv.... habe sonst keine Symthome entdeckt.

...zum Beitrag

Wie interaktiven Netzgraphen programmieren?

Hi,

bei so einem kleinen Projekt, das ich gerade mache, arbeite ich sehr viel mit Suchalgorithmen auf Netzgraphen. Die Algorithmik ist dabei eher weniger das Problem, sondern eher die interaktive Visualisierung der Netzgraphen.

Ich möchte diese nähmlich zunächst zeichnen (was mir auch gelungen ist) und anschließend mit der Maus verändern können (was mir noch nicht ganz gelungen ist). Dabei soll man die Knoten des Graphen verschieben können während sich die anliegenden Kanten entsprechen mitbewegen.

Ich habe das bis jetzt mit javafx gemacht und wäre sehr froh wenn ich das auch so weiterführen könnte. Dass andere Sprachen mein Problem sehr viel leichter lösen könnten, ist mir bewusst. Ich bin dementsprechend auch flexibel.

Danke schonmal im Voraus für die Antworten :)

...zum Beitrag

Javascript - JSON File in Array umwandeln?

Wie wandele ich einen JSON Datei in Arrays um. Ich bin dabei einen Graph mit Knoten und Kanten zu erstellen. Da möchte ich die unten genannte JSON Datei benutzen. Als Knoten ist dann der index (KayO, BenBeck usw.) und die Kanten sind dann die skills. Da kommt die Frage wie ich den JSON Datei in Array umwandeln möchte.

So sieht mein aktueller JSON Datei aus.

const persona = {
    "KayO": {
      firstname: "Kay",
      lastname: "Ohran",
      Birthdate: "11.09.64",
      Hobby: "footbal, tennis",
      City: "California",
      skills: "java, python, HTML, json",
    },
    BenBeck: {
      firstname: "Ben",
      lastname: "Beckamm",
      Birthdate: "03.95.87",
      Hobby: "football, programming, running",
      City: "New York",
      skills: "css, ruby, php, training, simulator, java, web, webgl, json",
    };

So soll es zum Schluss aussehen:

  const persona = {
    "KayO": [{
      firstname: "Kay",
      lastname: "Ohran",
      Birthdate: "11.09.64",
      Hobby: ["footbal, tennis"],
      City: "California",
      skills: ["java, python, HTML, json"],
    }],
    BenBeck: [{
      firstname: "Ben",
      lastname: "Beckamm",
      Birthdate: "03.95.87",
      Hobby: ["football, programming, running"],
      City: "New York",
      skills: ["css, ruby, php, training, simulator, java, web, webgl, json"],
    }]};

...zum Beitrag

Wie kann ich anhand eines Graphens eine Funktion aufstellen?

Hey,

ich habe im Unterricht nicht ganz verstanden wie man anhand des Graphens eine Funktion erstellt .Und jetzt ist meine Frage wie genau das funktioniert.

...zum Beitrag

Das Ding an sich - Kant

Gibt es 'Das Ding an sich' als Titel eines Textes von Kant oder ist es nur ein Begiff den er verwendet? Ich habe es als Hausaufgabe aufbekommen den Text dazu zu finden aber ich zweifele gerade daran, ob ich mich nicht vertan habe und es nur eine Begriffserklärung gibt.

...zum Beitrag

Wie implementiert man in Python eine Matrix?

Ich frage mich wie ich in Python ein Graphen als Adjazenzmatrix darstellte. Es sollte nicht in Listenform ( Liste=[ [2, 3] [6,8]] ) sein, wobei der äußere Listenindex eine Nummer für einen Knoten darstellt dem eine adjazenz zu geordnet werden soll.

...zum Beitrag

Wie zeichne ich einen Graph in Javascript D3.js?

Ich möchte ein Graphendiagramm erstellen. Dazu habe ich eine JSON-Datei erstellt. Die Skills ("java, python, HTML, json") sind die Knoten und die Indexe (KayO, BenBeck, Borea usw.) sind die Kanten. Der Knoten muss eine Mindestgröße haben und darf nicht zu groß werden. Anschließend möchte ich mit einem Klick auf den Knoten die Liste der Publikationen auf der rechten Seite aufrufen können. Dabei soll der aktuell ausgewählte Knoten in der Visualisierung hervorgehoben werden. Ich habe bereits aus diesem Beispiel (https://bl.ocks.org/heybignick/3faf257bbbbc7743bb72310d03b86ee8) was implementiert. Aber leider komme ich nicht weiter.

Diese ist meine JSON Datei:

const persona = {
    "KayO": {
      firstname: "Kay",
      lastname: "Ohran",
      City: "California",
      skills: "java, python, HTML, json",
    },
    BenBeck: {
      firstname: "Ben",
      lastname: "Beckamm",
      City: "New York",
      skills: "css, ruby, php, training, simulator, java, web, webgl, json",
    };

Das ist mein Code

    const bib = persona;
    console.table(bib);
    const graph = {nodes: [{id: "a"}, {id: "b"}], links: [{source: "a", target: "b"}]};
    const linkColor = d3.scaleLinear().domain([0, 1]).range(["#eee", "#000"]);

    const svg = d3.select("svg");
    const width = +svg.attr("width");
    const height = +svg.attr("height");

    const simulation = d3
      .forceSimulation()
      .force("link", d3.forceLink().id(function (d) { return d.id; }))
      .force("charge", d3.forceManyBody())
      .force("center", d3.forceCenter(width / 2, height / 2));

      //linien -> Kanten
      var link = svg.append("g").attr("class", "links")
      .selectAll("line")
      .data(graph.links).enter().append("line")
      .attr("stroke", "#aaa");

      //kreise -> Knoten
    var node = svg.append("g")
      .attr("class", "nodes")
      .selectAll("circle").data(graph.nodes).enter().append("circle")
      .attr("r", 5).call(d3.drag().on("start", dragstarted).on("drag", dragged).on("end", dragended));

    node.append("title").text(d => d.id);


    simulation.nodes(graph.nodes).on("tick", ticked)
simulation.force("link").links(graph.links);

    function ticked() {
      link
        .attr("x1", d => d.source.x)
        .attr("y1", d => d.source.y)
        .attr("x2", d => d.target.x)
        .attr("y2", d => d.target.y);
      node.attr("cx", d => d.x).attr("cy", d => d.y);
    }

    function dragstarted(event) {
      if (!event.active) simulation.alphaTarget(0.3).restart();
      event.subject.fx = event.subject.x;
      event.subject.fy = event.subject.y;
    }

    function dragged(event) {
      event.subject.fx = event.x;
      event.subject.fy = event.y;
    }

    function dragended(event) {
      if (!event.active) simulation.alphaTarget(0);
      event.subject.fx = null;
      event.subject.fy = null;
    }

...zum Beitrag

Was möchtest Du wissen?

Deine Frage stellen